admin管理员组文章数量:1593971
搞了很久的题目了
其实我们经常见到一类很明显的dp,它的状态转移方程为
f[i] = max{f[j]+(sum[i]-sum[j])^2}+C
时间复杂度O(n^2),当数据范围较大时无法通过全部数据,因此我们要进行优化
推荐一篇博文:http://blog.sina/s/blog_5f5353cc0100jx41.html
上面说得很清楚了,使用斜率优化的前提是
1.证明较优决策点对后续状态影响的持续性
2.求斜率方程
3.规定队列维护方法
说一下维护方法,我们知道对于j,k两个决策,若j<k且slope(j,k)<sum[i],那么k比j要好,由1可知对于所有的后继状态k都要比j好,直接删除j不予考虑。
因此,维护方式为
队首:比较slope(q1,q2)是否小于sum[i],若是,则删去q1,不能继续下去即为极值点
队尾:考虑插入一个新元素c,若slope(a,b)<sum[i],slope(b,c)<sum[i]则删除b,直到不能再删为止
其实还有种更好理解的方式,并且能够解决决策不完全单调的情况——数形结合
对于操作点i,若决策点j最优,那么必然有
f[i] = f[j]+(sum[i]-sum[j])^2
我们移项可以得到f[i]-sum[i]^2+2*sum[i]*sum[j] = f[j]+sum[j]^2
那么,计G=f[i]-sum[i]^2,xi=2*sum[i],yi=f[i]+sum[i]^2
我们希望G最大,那么我们可以理解为给定斜率为sum[i]的直线,经过给定点集中的任意一点截距最大为多少
很显然,决策点肯定在上凸壳上,因此我们只需要维护一个上凸壳,时间复杂度O(nlogn)
特别的,对于这种点集只增不减的情况,我们只需要使用单调队列即可
#include <cstdio>
using namespace std;
const int MAXN = 50001;
int n,l;
long long f[MAXN];
long long Q[MAXN];
long long sum[MAXN];
long long G(int k,int j)
{
return f[k]+(sum[k]+l)*(sum[k]+l)-f[j]-(sum[j]+l)*(sum[j]+l);
}
long long S(int k,int j)
{
return 2*(sum[k]-sum[j]);
}
int main()
{
scanf("%d%d",&n,&l);
l++;
for (int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
sum[i] = sum[i-1]+x;
}
for (int i=1;i<=n;i++) sum[i] += i;
int head = 0, tail = 0;
for (int i=1;i<=n;i++)
{
while (head < tail && G(Q[head+1],Q[head]) <= sum[i]*S(Q[head+1],Q[head])) head++;
int x = Q[head];
f[i] = f[x]+(sum[i]-sum[x]-l)*(sum[i]-sum[x]-l);
Q[++tail] = i;
for (int j=tail-1;j>head;j--)
{
if (G(Q[j+1],Q[j])*S(Q[j],Q[j-1]) <= G(Q[j],Q[j-1])*S(Q[j+1],Q[j])) Q[j] = Q[tail--];
else break;
}
}
printf("%lld\n",f[n]);
return 0;
}
顺便说一句,类似NOI2007 cash决策不完全单调的题目如果用Splay维护上凸壳会比较麻烦,建议使用cdq分治
版权声明:本文标题:斜率优化DP BZOJ 1010 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1728181484a1148427.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论