bzoj1563如何运用单调决策性DP解决？

本文共计1581个文字，预计阅读时间需要7分钟。

这个题目一看数字就感觉很爆炸啊！先不考虑他。

首先对长度加1，然后取前缀和设为a[i]，取到第i个句子作为当前行，设为d[i]。显然f(x)=|x|^p是一个下凸函数。

接下来，对于每个i，计算d[i]和a[i]的差值，并与d[j]和a[j]的差值进行比较，其中j从0到i-1。如果d[j]和a[j]的差值加上a[i]减去a[j]再减去L-1大于d[i]，则更新d[i]为这个新的值。

最后，输出f(x)的值。

这个题一看数字就很爆炸啊。。不过先不管他。。

先对长度+1，然后取个前缀和设为a

设d[i]为取到i个句子且当前行以i句结尾的最小代价

d[i]=max{d[j]+|a[i]-a[j]-L-1|^p}

显然f(x)=|x|^p是个下凸函数，即x越大导数越大。。

然后考虑2个决策点j<k<i

如果d[j]+|a[i]-a[j]-L-1|^p>d[k]+|a[i]-a[k]-L-1|^p，那么此后j就不会比k更优了。。

所以用单调队列存递增的决策点，用上面的式子去队尾就可以了。。

然而数非常爆炸，在比较的时候很麻烦，于是用long double(double都不行= =)来做大数比较，虽然有精度误差但是问题不大。。

复杂度O(Tnlognlogp)，常数巨大。。