CF933E A Preponderant Reunion DP

传送门


题解搬运工

设原问题为问题A。每一次减少$min{p_i , p_{i+1}}(难以处理,我们考虑将限制变得宽松一些:每一次可以减少)[1,min{p_i , p_{i+1}}](的任意值,需要满足的终止条件与问题A相同。我们称其为问题B,设区间)[l,r]$在问题B操作下的答案为$g_{l,r}$。显然问题B的答案要小于等于问题A。

再考虑:在问题AB中,最后的结果一定是两个正数之间有一段0。我们再考虑:设$f_{l,r}(表示只操作区间)[l,r](使得区间)[l,r]$的值全部小于等于$0$(可以为负)的最小代价,设其为问题C。不难发现:设$c_l = p_l$,(c_i = max{p_i - c_{i-1} , 0} , i in [l+1,r]),那么$f_{l,r} = sumlimits_^r c_i$。

首先,(f_{l,l} = g_{l-1,l+1})(f_{l,l+1} = g_{l-1,l+2}),而

(f_{l,r} = sumlimits_{i=l}^rc_i = sumlimits_{i=l}^{r-2}c_i + c_{r-1} + max{p_r - c_{r-1} , 0} = f_{l,r-2} + max{p_r , c_{r-1}} geq f_{l,r-2} + f_{r,r})

不难发现中间漏掉了一个$r-1$,相当于$r-1$不变为$0$,而$[l,r-2](和)[r,r]$变为$0$,也就是说在最优情况中$r-1$会保留下来,即$g_{l-1,r+1} = g_{l-1,r-1} + g_{r-1,r+1}$。不断递归下去就可以知道$g_{l-1,r+1}$的最优情况中,极长的$0$连续段不会超过$2$。

因为极长$0$段小于等于$2$,所以问题C中不会出现负数,所以问题C中构造的解在问题B中一定满足。至此我们完成了C到B的转化。

同时注意到问题B中的所有操作一定会让若干个数变为$0$,所以在问题B中的可行操作在问题A中也一定可行(这个感性理解好了,不知道怎么严格证明),即在问题A中极长连续$0$段长度不会超过$2$

接下来考虑DP:设$f_$表示以$i$结尾、选择$i$的$[1,i]$的最优答案,转移考虑其之前选择多少个$0$,并记下转移点。值得注意的是如果存在两个$0$,那么最少步数一定是$max{p_ , p_}$,即先对$p_ , p_$做一次,剩下的一次再做完。最后还原DP结果输出构造方案即可。

值得注意的一点是如果$f_i$的操作过程中使得某个数变为负数是一定不优的,由问题C就可以知道这一点。

代码

原文地址:https://www.cnblogs.com/Itst/p/11160621.html