[关闭]
@KirinBill 2018-03-27T12:42:15.000000Z 字数 18697 阅读 1937

DP优化——斜率优化

动态规划

目录


思想

例题:[HNOI 2008] 玩具装箱

UmDIe.png

代码:

  1. #include <cstdio>
  2. const int MAXN=50005;
  3. int n,l;
  4. long long k[MAXN],dp[MAXN];
  5. inline long long sqr(register long long x){return x*x;}
  6. //intercept
  7. inline long long y_itcpt(int i){
  8. return sqr(k[i])+(l*k[i]<<1)+dp[i];
  9. }
  10. inline long long slope(int i){return -(k[i]<<1);}
  11. inline long long cal(int i,int j){
  12. return slope(j)*k[i]+y_itcpt(j);
  13. }
  14. //intersection
  15. inline double itsct(int i,int j){
  16. return (double)(y_itcpt(j)-y_itcpt(i))/(slope(i)-slope(j));
  17. }
  18. inline long long slopeDP(){
  19. static int dq[MAXN];
  20. int head=0,tail=0;
  21. for(int i=1;i<=n;++i){
  22. while(head<tail && cal(i,dq[head])>=cal(i,dq[head+1]))
  23. ++head;
  24. dp[i]=cal(i,dq[head])+sqr(k[i]-l);
  25. while(head<tail && itsct(i,dq[tail-1])<=itsct(dq[tail],dq[tail-1]))
  26. --tail;
  27. dq[++tail]=i;
  28. }
  29. return dp[n];
  30. }
  31. int main(){
  32. scanf("%d%d",&n,&l);
  33. ++l;
  34. for(int i=1;i<=n;++i){
  35. scanf("%d",&k[i]);
  36. k[i]+=k[i-1];
  37. }
  38. for(int i=1;i<=n;++i)
  39. k[i]+=i;
  40. printf("%lld",slopeDP());
  41. return 0;
  42. }

练习

普通斜率优化

1.[BZOJ 1597] 土地购买

代码:

  1. #include <cstdio>
  2. #include <algorithm>
  3. using std::sort;
  4. const int MAXN=50005;
  5. int n;
  6. long long dp[MAXN];
  7. struct square{
  8. int a,b;
  9. static bool cmp_ab(const square &a,const square &b){
  10. return a.a<b.a || (a.a==b.a && a.b<b.b);
  11. }
  12. }field[MAXN],tmp[MAXN];
  13. inline int slope(int i){return field[i+1].b;}
  14. inline long long y_itcpt(int i){return dp[i];}
  15. inline long long cal(int i,int j){
  16. return (long long)slope(j)*field[i].a+y_itcpt(j);
  17. }
  18. inline double itsct(int i,int j){
  19. return (double)(y_itcpt(j)-y_itcpt(i))/(slope(i)-slope(j));
  20. }
  21. inline long long slopeDP(){
  22. static int dq[MAXN];
  23. int head=0,tail=0;
  24. for(int i=1;i<=n;++i){
  25. while(head<tail && cal(i,dq[head])>=cal(i,dq[head+1]))
  26. ++head;
  27. dp[i]=cal(i,dq[head]);
  28. while(head<tail && itsct(i,dq[tail-1])<=itsct(dq[tail],dq[tail-1]))
  29. --tail;
  30. dq[++tail]=i;
  31. }
  32. return dp[n];
  33. }
  34. int main(){
  35. scanf("%d",&n);
  36. for(int i=1;i<=n;++i)
  37. scanf("%d%d",&tmp[i].a,&tmp[i].b);
  38. sort(tmp+1,tmp+n+1,square::cmp_ab);
  39. int cnt=0;
  40. for(int i=1;i<=n;++i){
  41. while(cnt && field[cnt].b<=tmp[i].b)
  42. --cnt;
  43. field[++cnt]=tmp[i];
  44. }
  45. n=cnt;
  46. printf("%lld",slopeDP());
  47. return 0;
  48. }

2.[ZJOI 2007] 仓库建设

代码:

  1. #include <cstdio>
  2. const int MAXN=1000005;
  3. int n;
  4. int dis[MAXN],c[MAXN],p[MAXN];
  5. long long sum[MAXN],sum_dis[MAXN],dp[MAXN];
  6. inline long long slope(int i){return sum[i];}
  7. inline long long y_itcpt(int i){return dp[i]-sum_dis[i];}
  8. inline long long cal(int i,int j){
  9. return slope(j)*dis[i]+y_itcpt(j);
  10. }
  11. inline double itsct(int i,int j){
  12. return (double)(y_itcpt(j)-y_itcpt(i))/(slope(i)-slope(j));
  13. }
  14. inline long long slopeDP(){
  15. static int dq[MAXN];
  16. int head=0,tail=0;
  17. for(int i=1;i<=n;++i){
  18. while(head<tail && cal(i,dq[head])>=cal(i,dq[head+1]))
  19. ++head;
  20. dp[i]=cal(i,dq[head])+c[i]-dis[i]*sum[i]+sum_dis[i];
  21. while(head<tail && itsct(i,dq[tail-1])>=itsct(dq[tail],dq[tail-1]))
  22. --tail;
  23. dq[++tail]=i;
  24. }
  25. return dp[n];
  26. }
  27. inline void pre_cal(){
  28. for(int i=1;i<=n;++i){
  29. dis[i]=dis[n]-dis[i];
  30. sum[i]=sum[i-1]+p[i];
  31. sum_dis[i]=sum_dis[i-1]+(long long)p[i]*dis[i];
  32. }
  33. }
  34. int main(){
  35. scanf("%d",&n);
  36. for(int i=1;i<=n;++i)
  37. scanf("%d%d%d",&dis[i],&p[i],&c[i]);
  38. pre_cal();
  39. printf("%lld",slopeDP());
  40. return 0;
  41. }

3.[BZOJ 3437]小P的牧场

代码:

  1. #include <cstdio>
  2. const int MAXN=1000005;
  3. int n;
  4. int a[MAXN],b[MAXN];
  5. long long sum[MAXN],sum_dis[MAXN],dp[MAXN];
  6. inline long long slope(int i){return sum[i];}
  7. inline long long y_itcpt(int i){
  8. return dp[i]-sum_dis[i];
  9. }
  10. inline long long cal(int i,int j){
  11. return slope(j)*(n-i)+y_itcpt(j);
  12. }
  13. inline double itsct(int i,int j){
  14. return (double)(y_itcpt(j)-y_itcpt(i))/(slope(i)-slope(j));
  15. }
  16. inline long long slopeDP(){
  17. static int dq[MAXN];
  18. int head=0,tail=0;
  19. for(int i=1;i<=n;++i){
  20. while(head<tail && cal(i,dq[head])>=cal(i,dq[head+1]))
  21. ++head;
  22. dp[i]=cal(i,dq[head])+sum_dis[i]-(n-i)*sum[i]+a[i];
  23. while(head<tail && itsct(i,dq[tail-1])>=itsct(dq[tail],dq[tail-1]))
  24. --tail;
  25. dq[++tail]=i;
  26. }
  27. return dp[n];
  28. }
  29. inline void pre_cal(){
  30. for(int i=1;i<=n;++i){
  31. sum[i]=sum[i-1]+b[i];
  32. sum_dis[i]=sum_dis[i-1]+(long long)(n-i)*b[i];
  33. }
  34. }
  35. int main(){
  36. scanf("%d",&n);
  37. for(int i=1;i<=n;++i)
  38. scanf("%d",&a[i]);
  39. for(int i=1;i<=n;++i)
  40. scanf("%d",&b[i]);
  41. pre_cal();
  42. printf("%lld",slopeDP());
  43. return 0;
  44. }

4.[BZOJ 3156] 防御准备

代码:

  1. #include <cstdio>
  2. const int MAXN=1e6+5;
  3. int n;
  4. int a[MAXN];
  5. long long dp[MAXN];
  6. inline long long sqr(register long long x){return x*x;}
  7. inline int slope(int i){return -i;}
  8. inline long long y_itcpt(int i){
  9. return dp[i]+(sqr(i)+i>>1);
  10. }
  11. inline long long cal(int i,int j){
  12. return (long long)slope(j)*i+y_itcpt(j);
  13. }
  14. inline double itsct(int i,int j){
  15. return (double)(y_itcpt(j)-y_itcpt(i))/(slope(i)-slope(j));
  16. }
  17. inline long long slopeDP(){
  18. static int dq[MAXN];
  19. int head=0,tail=0;
  20. for(int i=1;i<=n;++i){
  21. while(head<tail && cal(i,dq[head])>=cal(i,dq[head+1]))
  22. ++head;
  23. dp[i]=cal(i,dq[head])+(sqr(i)-i>>1)+a[i];
  24. while(head<tail && itsct(i,dq[tail-1])<=itsct(dq[tail],dq[tail-1]))
  25. --tail;
  26. dq[++tail]=i;
  27. }
  28. return dp[n];
  29. }
  30. int main(){
  31. scanf("%d",&n);
  32. for(int i=1;i<=n;++i)
  33. scanf("%d",&a[i]);
  34. printf("%lld",slopeDP());
  35. return 0;
  36. }

5.[APIO 2010] 特别行动队

代码:

  1. #include <cstdio>
  2. const int MAXN=1000005;
  3. int n,a,b,c;
  4. int sum[MAXN];
  5. long long dp[MAXN];
  6. inline long long sqr(register long long x){return x*x;}
  7. inline long long slope(int i){
  8. return (long long)-(a<<1)*sum[i];
  9. }
  10. inline long long y_itcpt(int i){
  11. return dp[i]+a*sqr(sum[i])-(long long)b*sum[i];
  12. }
  13. inline long long cal(int i,int j){
  14. return slope(j)*sum[i]+y_itcpt(j);
  15. }
  16. inline double itsct(int i,int j){
  17. return (double)(y_itcpt(j)-y_itcpt(i))/(slope(i)-slope(j));
  18. }
  19. inline long long slopeDP(){
  20. static int dq[MAXN];
  21. int head=0,tail=0;
  22. for(int i=1;i<=n;++i){
  23. while(head<tail && cal(i,dq[head])<=cal(i,dq[head+1]))
  24. ++head;
  25. dp[i]=cal(i,dq[head])+a*sqr(sum[i])+(long long)b*sum[i]+c;
  26. while(head<tail && itsct(i,dq[tail-1])<=itsct(dq[tail],dq[tail-1]))
  27. --tail;
  28. dq[++tail]=i;
  29. }
  30. return dp[n];
  31. }
  32. int main(){
  33. scanf("%d",&n);
  34. scanf("%d%d%d",&a,&b,&c);
  35. for(int i=1;i<=n;++i){
  36. scanf("%d",&sum[i]);
  37. sum[i]+=sum[i-1];
  38. }
  39. printf("%lld",slopeDP());
  40. return 0;
  41. }

6.[SDOI 2016] 征途

代码:

  1. #include <cstdio>
  2. const int MAXN=3005;
  3. int n,m;
  4. int sum[MAXN];
  5. long long dp[MAXN][MAXN];
  6. inline long long sqr(register long long x){return x*x;}
  7. inline long long slope(int i){return -(sum[i]<<1);}
  8. inline long long y_itcpt(int i,int k){
  9. return dp[k][i]+sqr(sum[i]);
  10. }
  11. inline long long cal(int i,int j,int k){
  12. return slope(j)*sum[i]+y_itcpt(j,k);
  13. }
  14. inline double itsct(int i,int j,int k){
  15. return (double)(y_itcpt(j,k)-y_itcpt(i,k))/(slope(i)-slope(j));
  16. }
  17. inline long long slopeDP(){
  18. static int dq[MAXN];
  19. for(int i=1;i<=n;++i)
  20. dp[1][i]=sqr(sum[i]);
  21. for(int i=2,head,tail;i<=m;++i){
  22. head=tail=0,dq[0]=i-1;
  23. for(int j=i;j<=n;++j){
  24. while(head<tail && cal(j,dq[head],i-1)>=cal(j,dq[head+1],i-1))
  25. ++head;
  26. dp[i][j]=cal(j,dq[head],i-1)+sqr(sum[j]);
  27. while(head<tail && itsct(j,dq[tail-1],i-1)<=itsct(dq[tail],dq[tail-1],i-1))
  28. --tail;
  29. dq[++tail]=j;
  30. }
  31. }
  32. return m*dp[m][n]-sqr(sum[n]);
  33. }
  34. int main(){
  35. scanf("%d%d",&n,&m);
  36. for(int i=1;i<=n;++i){
  37. scanf("%d",&sum[i]);
  38. sum[i]+=sum[i-1];
  39. }
  40. printf("%lld",slopeDP());
  41. return 0;
  42. }

7.[APIO 2014] 序列分割

代码:

  1. #include <cstdio>
  2. const int MAXN=100005;
  3. //const int MAXK=205;
  4. int n,k;
  5. int sum[MAXN];
  6. //int pre[MAXK][MAXN];
  7. long long dp[2][MAXN];
  8. inline long long sqr(register long long x){return x*x;}
  9. inline int slope(int i){return sum[i];}
  10. inline long long y_itcpt(int i,int k){
  11. return dp[k&1][i]-sqr(sum[i]);
  12. }
  13. inline long long cal(int i,int j,int k){
  14. return (long long)slope(j)*sum[i]+y_itcpt(j,k);
  15. }
  16. inline double itsct(int i,int j,int k){
  17. return (double)(y_itcpt(j,k)-y_itcpt(i,k))/(slope(i)-slope(j));
  18. }
  19. inline long long slopeDP(){
  20. static int dq[MAXN];
  21. for(int i=1,head,tail;i<=k;++i){
  22. for(int j=1;j<=i;++j)
  23. dp[i&1][j]=0;
  24. head=tail=0,dq[0]=i;
  25. for(int j=i+1;j<=n;++j){
  26. while(head<tail && cal(j,dq[head],i-1)<=cal(j,dq[head+1],i-1))
  27. ++head;
  28. //pre[i][j]=dq[head];
  29. dp[i&1][j]=cal(j,dq[head],i-1);
  30. while(head<tail && itsct(j,dq[tail-1],i-1)<=itsct(dq[tail],dq[tail-1],i-1))
  31. --tail;
  32. if(slope(j)!=slope(dq[tail])) dq[++tail]=j;
  33. }
  34. }
  35. return dp[k&1][n];
  36. }
  37. int main(){
  38. scanf("%d%d",&n,&k);
  39. for(int i=1;i<=n;++i){
  40. scanf("%d",&sum[i]);
  41. sum[i]+=sum[i-1];
  42. }
  43. printf("%lld",slopeDP());
  44. /*
  45. putchar('\n');
  46. for(int i=k,j=n;i;--i){
  47. j=pre[i][j];
  48. printf("%d ",j);
  49. }
  50. */
  51. return 0;
  52. }

二分不单调决策

上面的练习都有一个共同的特点,就是自变量是单调的,这样我们每次可以将双端队列的开头直线不断弹出,让对于当前自变量的最优决策在队首。然而有一些题比较坑,自变量并不单调,这时我们不能再像之前那样弹队首了,只能通过二分来查找对于当前自变量的最优决策了。

1.[SDOI 2012] 任务安排
BZOJ上题面不完整。。。

任务按标号从~的顺序分批完成,不是任意顺序。 INT_MAX LLONG_MAX.

代码:

  1. #include <cstdio>
  2. const int MAXN=300005;
  3. int n,s,top;
  4. int stk[MAXN];
  5. long long sumt[MAXN],sumf[MAXN],dp[MAXN];
  6. inline long long slope(int i){return -sumf[i];}
  7. inline long long y_itcpt(int i){
  8. return dp[i]-sumf[i]*s;
  9. }
  10. inline long long cal(int i,int j){
  11. return slope(j)*sumt[i]+y_itcpt(j);
  12. }
  13. inline double itsct(int i,int j){
  14. return (double)(y_itcpt(j)-y_itcpt(i))/(slope(i)-slope(j));
  15. }
  16. inline int bin_chop(int now){
  17. int l=1,r=top,mid;
  18. while(l<=r){
  19. mid=l+r>>1;
  20. if(itsct(stk[mid],stk[mid-1])<=sumt[now])
  21. l=mid+1;
  22. else r=mid-1;
  23. }
  24. return stk[r];
  25. }
  26. inline long long slopeDP(){
  27. for(int i=1;i<=n;++i){
  28. dp[i]=cal(i,bin_chop(i))+sumt[i]*sumf[i]+sumf[n]*s;
  29. while(top && itsct(i,stk[top-1])<=itsct(stk[top],stk[top-1]))
  30. --top;
  31. if(slope(i)!=slope(stk[top])) stk[++top]=i;
  32. }
  33. return dp[n];
  34. }
  35. int main(){
  36. scanf("%d%d",&n,&s);
  37. for(int i=1;i<=n;++i){
  38. scanf("%lld%lld",&sumt[i],&sumf[i]);
  39. sumt[i]+=sumt[i-1],sumf[i]+=sumf[i-1];
  40. }
  41. printf("%lld",slopeDP());
  42. return 0;
  43. }

2.[CEOI 2009] harbingers

代码:

  1. #include <cstdio>
  2. const int MAXN=100005;
  3. int n;
  4. int v[MAXN],w[MAXN];
  5. int he[MAXN],dis[MAXN];
  6. int stk[MAXN];
  7. long long dp[MAXN];
  8. struct line{int to,nex,w;}ed[MAXN<<1];
  9. inline void addE(int u,int v,int w){
  10. static int cnt;
  11. ed[++cnt]=(line){v,he[u],w};
  12. he[u]=cnt;
  13. }
  14. inline int slope(int i){return -dis[i];}
  15. inline long long y_itcpt(int i){return dp[i];}
  16. inline long long cal(int i,int j){
  17. return (long long)slope(j)*v[i]+dp[j];
  18. }
  19. inline double itsct(int i,int j){
  20. return (double)(y_itcpt(j)-y_itcpt(i))/(slope(i)-slope(j));
  21. }
  22. inline int bin_chop_ln(int now,int r){
  23. int l=1,mid;
  24. while(l<=r){
  25. mid=l+r>>1;
  26. if(itsct(stk[mid-1],stk[mid])<=v[now])
  27. l=mid+1;
  28. else r=mid-1;
  29. }
  30. return stk[r];
  31. }
  32. inline long long slopeDP(int i,int top){
  33. return cal(i,bin_chop_ln(i,top))+w[i]+(long long)v[i]*dis[i];
  34. }
  35. inline int bin_chop_top(int now,int r){
  36. int l=1,mid;
  37. while(l<=r){
  38. mid=l+r>>1;
  39. if(itsct(now,stk[mid-1])>itsct(stk[mid],stk[mid-1]))
  40. l=mid+1;
  41. else r=mid-1;
  42. }
  43. return r;
  44. }
  45. void treeDP(int u,int fa,int top){
  46. dp[u]=slopeDP(u,top);
  47. top=bin_chop_top(u,top);
  48. int back_cur=++top,pre=stk[top];
  49. stk[top]=u;
  50. for(int i=he[u],v;i;i=ed[i].nex){
  51. v=ed[i].to;
  52. if(v!=fa){
  53. dis[v]=dis[u]+ed[i].w;
  54. treeDP(v,u,top);
  55. }
  56. }
  57. stk[back_cur]=pre;
  58. }
  59. int main(){
  60. scanf("%d",&n);
  61. for(int i=1,u,v,w;i<n;++i){
  62. scanf("%d%d%d",&u,&v,&w);
  63. addE(u,v,w),addE(v,u,w);
  64. }
  65. for(int i=2;i<=n;++i)
  66. scanf("%d%d",&w[i],&v[i]);
  67. for(int i=he[1],v;i;i=ed[i].nex){
  68. v=ed[i].to;
  69. dis[v]=ed[i].w;
  70. treeDP(v,1,0);
  71. }
  72. for(int i=2;i<=n;++i){
  73. printf("%lld",dp[i]);
  74. if(i!=n) putchar(' '); //卡输出
  75. }
  76. return 0;
  77. }

CDQ分治维护凸壳

上一个部分的题虽然自变量不单调了,但是直线斜率还是单调的,依然可以用双端队列或者栈维护。但是有些丧病的出题人把斜率也给搞的不单调了,这时只能用一些方法维护一个可以迅速从中间插入的凸壳了,传统方法是平衡树,但是那样代码量很大,常数也不小,而考虑到这里是可以离线维护的,我们可以用CDQ分治来解决(陈丹琪的论文就是用这个引入的Orz)。

1.[NOI 2007] 货币兑换

代码:

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <cstring>
  4. using std::sort;
  5. using std::max;
  6. const int MAXN=100005;
  7. int n;
  8. double a[MAXN],b[MAXN],rate[MAXN],ans[MAXN];
  9. struct dp_arr{
  10. int id;
  11. double a,b,x;
  12. double *ans;
  13. static bool cmp_x(const dp_arr &a,const dp_arr &b){
  14. return a.x<b.x;
  15. }
  16. }dp[MAXN];
  17. inline double slope(int i){return dp[i].a;}
  18. inline double y_itcpt(int i){return dp[i].b;}
  19. inline double cal(int i,int j){
  20. return slope(j)*dp[i].x+y_itcpt(j);
  21. }
  22. inline double itsct(int i,int j){
  23. return (y_itcpt(j)-y_itcpt(i))/(slope(i)-slope(j));
  24. }
  25. inline void separate(int l,int r){
  26. static dp_arr tmp[MAXN];
  27. int mid=l+r>>1;
  28. for(int cur=l,lp=l,rp=mid+1;cur<=r;++cur){
  29. if(dp[cur].id<=mid) tmp[lp++]=dp[cur];
  30. else tmp[rp++]=dp[cur];
  31. }
  32. memcpy(dp+l,tmp+l,(r-l+1)*sizeof(dp_arr));
  33. }
  34. inline void slopeDP(int l,int r){
  35. static int dq[MAXN];
  36. int mid=l+r>>1;
  37. int head=0,tail=0;
  38. for(int i=l;i<=mid;++i){
  39. while(head<tail && itsct(i,dq[tail-1])<=itsct(dq[tail],dq[tail-1]))
  40. --tail;
  41. if(slope(i)!=slope(dq[tail])) dq[++tail]=i;
  42. }
  43. for(int i=mid+1;i<=r;++i){
  44. while(head<tail && cal(i,dq[head])<=cal(i,dq[head+1]))
  45. ++head;
  46. *dp[i].ans=max(*dp[i].ans,b[dp[i].id]*cal(i,dq[head]));
  47. }
  48. }
  49. void CDQ_DC(int l,int r){
  50. static dp_arr tmp[MAXN];
  51. if(l==r){
  52. //其实l=dp[l].id,但是现在dp[l-1].id可能不等于l了
  53. //所以这样写
  54. *dp[l].ans=max(*dp[l].ans,ans[dp[l].id-1]);
  55. dp[l].b=*dp[l].ans/(a[l]*rate[l]+b[l]);
  56. dp[l].a=dp[l].b*rate[l];
  57. return;
  58. }
  59. separate(l,r);
  60. int mid=l+r>>1;
  61. CDQ_DC(l,mid);
  62. slopeDP(l,r);
  63. CDQ_DC(mid+1,r);
  64. for(int cur=l,lp=l,rp=mid+1;cur<=r;++cur){
  65. if(rp>r || (lp<=mid && dp[lp].a<=dp[rp].a))
  66. tmp[cur]=dp[lp++];
  67. else tmp[cur]=dp[rp++];
  68. }
  69. memcpy(dp+l,tmp+l,(r-l+1)*sizeof(dp_arr));
  70. }
  71. int main(){
  72. scanf("%d%lf",&n,&ans[0]);
  73. dp[0].ans=&ans[0];
  74. for(int i=1;i<=n;++i){
  75. scanf("%lf%lf%lf",&a[i],&b[i],&rate[i]);
  76. dp[i].x=a[i]/b[i];
  77. dp[i].id=i,dp[i].ans=&ans[i];
  78. }
  79. sort(dp+1,dp+n+1,dp_arr::cmp_x);
  80. CDQ_DC(1,n);
  81. printf("%.3lf",ans[n]);
  82. return 0;
  83. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注