题解：CF573D Bear and Cavalry

· · 题解

Bear and Cavalry

逆天冲刺 NOIP 题单可做题之七。

经过 @wang54321 的讲解我大概懂了这道题怎么写了，拜谢大佬。

首先我们考虑一个弱化版的问题，如果没有每个士兵不能骑自己的马如何解决？

很明显可以直接排序，然后用排序后的 w_i 和 h_i 相乘即可。

不能骑自己的马明显也需要排序，我们先记录每个马对应的士兵是谁，然后考虑分类讨论。

如果此时的 w_i 和 h_i 并不对应就可以直接将二者连起来

如果此时的 w_i 和 h_i 对应肯定要考虑形成这样的图形

也就是让 w_{i} 和 h_{i+1} 连起来，w_{i+1} 和 h_i 连起来，可以发现这样是最优的

如果 w_{i} 和 h_{i} 对应，w_{i+1} 和 h_{i+1} 对应，w_{i+2} 和 h_{i+2} 对应（连续三个对应起来的）怎么办呢。

如果我们还是让 w_{i} 和 h_{i+1} 连起来，w_{i+1} 和 h_i 连起来，此时最后的 w_{i+2} 和 h_{i+2} 只能对应起来，那么我们就输透了。

所以我们考虑用其他方式维护，也就是形成这样的图形

如果有超过三个呢？假设有 4 个连续对应的，我们发现可以拆成两个第二个图形。

那么我们就能发现在图中就只会存在上图内的 4 种图形，本题也就迎刃而解了。

然后设 f_i 表示前 i 个点匹配的答案，能列出 O(nq) 转移方程，卡卡常就能过。

f_i=\max \begin{cases} f_{i-1}+w_i\times h_i \\ f_{i-2}+w_i\times h_{i−1}+w_{i-1}\times h_i\\ f_{i−3}+w_i\times h_{i−1}+w_{i−1}\times h_{i−2}+w_{i−2}\times h_i\\ f_{i−3}+w_i\times h_{i−2}+w_{i−1}\times h_{i}+w_{i−2}\times h_{i-1}\\ \end{cases}