现在的位置: 首页 > 综合 > 正文

dp四边形优化

2018年02月21日 ⁄ 综合 ⁄ 共 8984字 ⁄ 字号 小 中 大 ⁄ 评论关闭

转载地址：点击打开链接

一、四边形不等式基本理论

在动态规划的转移方程中，常见这样一种转移方程：

这两个定理证明在赵爽的《动态规划加速原理之四边形不等式》中给出了相关的证明。

二、四边形定理的应用

1、poj1160 题目大意：给定n个城市，在m个城市里建邮局，使所有城市到最近邮局的距离和最小。很容易得到这样的方程：

dp(i,j)=min(dp(i-1,k)+w(k+1,j)) , i-1<=k<j  s(i-1,j)<=k<=s(i,j+1)

w(i,j)=w(i,j-1)+val[j]-val[(j+i)/2] , i<j<=n

dp(1,i)=w(1,i), w(i,i)=0, s(1,i)=0

对于函数w(i,j)有人可能疑问，从i到j建一座邮局，对于邮局位置k,(i<=k<=j)，这是一个凹区间，k选在i ,j的中间位置w(i,j)才是最小的，如何j-i是一个奇数，那么中间的两个数都是距离最小的点。对于w满足四边形不等式和区间单调性（本人表示不大会证，一般动态转移方程类似，n^3不能解决的问题，都是这么搞吧）。于是，我们限制了原方程中k的取值范围，得到了O(n^2)算法。

 

[cpp] view
plaincopy

  1. #include <iostream>  
  2. #include <cstdio>  
  3. using namespace std;  
  4. #define inf 0x7ffffff  
  5. #define MIN(a,b) ((a)<(b)?(a):(b))  
  6. int dp[31][301];  
  7. int val[301];  
  8. int w[301][301];  
  9. int s[31][301];//表示前i-1个邮局的城市数  
  10. int main()  
  11. {  
  12.     int n,m;  
  13.     while(~scanf("%d%d",&n,&m))  
  14.     {  
  15.         for(int i=1;i<=n;++i)  
  16.         {  
  17.             scanf("%d",&val[i]);  
  18.         }  
  19.         for(int i=1;i<=n;++i)  
  20.         {  
  21.             w[i][i]=0;  
  22.             for(int j=i+1;j<=n;++j)  
  23.             {  
  24.                 w[i][j]=w[i][j-1]+val[j]-val[(i+j)/2];  
  25.             }  
  26.           
  27.         }  
  28.         for(int i=1;i<=n;++i)  
  29.         {  
  30.             for(int j=1;j<=m;++j)  
  31.             {  
  32.                 dp[j][i]=inf;  
  33.             }  
  34.         }  
  35.         for(int i=1;i<=n;++i)  
  36.         {  
  37.             dp[1][i]=w[1][i];  
  38.             s[1][i]=0;  
  39.         }  
  40.         for(int i=2;i<=m;++i)  
  41.         {  
  42.             s[i][n+1]=n;  
  43.             for(int j=n;j>i;--j)  
  44.             {  
  45.                 for(int k=s[i-1][j];k<=s[i][j+1];++k)  
  46.                 {  
  47.                     if(dp[i-1][k]+w[k+1][j]<dp[i][j])  
  48.                     {  
  49.                         s[i][j]=k;  
  50.                     }  
  51.                     dp[i][j]=MIN(dp[i][j],dp[i-1][k]+w[k+1][j]);  
  52.                 }  
  53.             }  
  54.         }  
  55.         printf("%d\n",dp[m][n]);  
  56.     }  
  57.     return 0;  
  58. }  

2、hdu2829题目大意：给定一个长度为n的序列，至多将序列分成m段，每段序列都有权值，权值为序列内两个数两两相乘之和。m<=n<=1000. 令权值最小。

状态转移方程很好想，dp[i][j] = min(dp[i][j],dp[i-1][k]+w[k+1][j])(1<=k<i)

通写法是n*n*m，当n为1000时运算量为10亿级别，必须优化。

四边形不等式优化，主要是减少枚举k的次数。w[i][j]是某段区间的权值，当区间变大，权值也随之变大，区间变小，权值也随之变小，此时就可以用四边形不等式优化。
我们设s[i][j]为dp[i][j]的前导状态，即：dp[i][j]=dp[i-1][s[i][j]]+ w[s[i][j]+1][j].之后我们枚举k的时候只要枚举s[i-1][j]<=k<=s[i][j+1],此时i必须从小到大遍历，j必须从大到小

[cpp] view
plaincopy

  1. #include <iostream>  
  2. #include <cstdio>  
  3. #include <cstring>  
  4. using namespace std;  
  5. #define min(a,b) ((a)<(b)?(a):(b))  
  6. #define LL long long  
  7. #define inf (LL)1<<60  
  8. LL dp[1002][1002];  
  9. LL w[1002][1002];  
  10. LL s[1002][1002];  
  11. LL p[1002];  
  12. LL val[1002][1002];  
  13. int main()  
  14. {  
  15.     int m,n;  
  16.     while(~scanf("%d%d",&n,&m))  
  17.     {  
  18.         if(!n&&!m)break;  
  19.         for(int i=1;i<=n;++i)  
  20.         {  
  21.             scanf("%lld",&p[i]);  
  22.         }  
  23.         memset(dp,0,sizeof(dp));  
  24.         memset(w,0,sizeof(w));  
  25.         memset(val,0,sizeof(val));  
  26.         for(int i=1;i<n;++i)  
  27.         {  
  28.             for(int j=i+1;j<=n;++j)  
  29.             {  
  30.                 val[i][j]=val[i][j-1]+p[i]*p[j];  
  31.             }  
  32.         }  
  33.         for(int i=n-1;i>=1;--i)  
  34.         {  
  35.             for(int j=i+1;j<=n;++j)  
  36.             {  
  37.                 w[i][j]=w[i+1][j]+val[i][j];  
  38.             }  
  39.         }  
  40.         for(int i=1;i<=m+1;i++)  
  41.         {  
  42.             for(int j=i+1;j<=n;++j)  
  43.             {  
  44.                 dp[i][j]=inf;  
  45.             }  
  46.         }  
  47.         for(int i=1;i<=n;++i)  
  48.         {  
  49.             dp[1][i]=w[1][i];  
  50.             s[1][i]=0;  
  51.         }  
  52.         for(int i=2;i<=m+1;++i)  
  53.         {  
  54.             s[i][n+1]=n;  
  55.             for(int j=n;j>i;--j)  
  56.             {  
  57.                 for(int k=s[i-1][j];k<=s[i][j+1];++k)  
  58.                 {  
  59.                     LL tmp=dp[i-1][k]+w[k+1][j];  
  60.             //      cout<<i<<' '<<j<<' '<<k<<' '<<tmp<<endl;  
  61.                     if(tmp<dp[i][j])  
  62.                     {  
  63.                         dp[i][j]=tmp;  
  64.                         s[i][j]=k;  
  65.                     }  
  66.                 }  
  67.             }  
  68.         }  
  69.         if(m+1>=n){dp[m+1][n]=0;}  
  70.         printf("%lld\n",dp[m+1][n]);  
  71.     }  


 

3、hdu3480 题目大意：给出n个数字，要你把这n个数字分成m堆，每一堆的价值是(max(val) - min(val)) ^ 2 要你求出分成m堆之后得到的最小价值 

设dp[i][j]表示前j个数字，分成i堆的最小价值。分析得到，当i<j<k<l，val[i] < val[j] < val[k] < val[l]的话，能得到最优值 因此先排序，然后容易得到式子dp[i][j] = min(dp[i - 1][k] + (val[j] - val[k + 1]) ^ 2) 这条就是典型的符合单调性的转移方程 因此直接套四边形不等式就可以解决了

[cpp] view
plaincopy

  1. #include <iostream>  
  2. #include <cstdio>  
  3. #include <algorithm>  
  4. #include <cstring>  
  5. using namespace std;  
  6. #define LL long long   
  7. #define inf 0x6fffffff  
  8. int dp[5002][10002];  
  9. int p[10002];  
  10. int s[5002][10002];  
  11. int cmp(const void *a,const void *b)  
  12. {  
  13.     return *(int*)a-*(int*)b;  
  14. }  
  15. int main()  
  16. {  
  17.     int cas,m,n,c;  
  18.     while(~scanf("%d",&cas))  
  19.     {  
  20.         c=1;  
  21.         while(cas--)  
  22.         {  
  23.             scanf("%d%d",&n,&m);  
  24.             for(int i=1;i<=n;++i)  
  25.             {  
  26.                 scanf("%d",&p[i]);  
  27.             }  
  28.             qsort(p+1,n,sizeof(p[0]),cmp);  
  29.             memset(s,0,sizeof(s));  
  30.             for(int i=1;i<=m;++i)  
  31.             {  
  32.                 for(int j=i;j<=n;++j)  
  33.                 {  
  34.                     if(j<=i){dp[i][j]=0;}  
  35.                     else    {dp[i][j]=inf;}  
  36.                 }  
  37.             }  
  38.             for(int i=1;i<=n;++i)  
  39.             {  
  40.                 s[1][i]=0;  
  41.                 dp[1][i]=(p[i]-p[1])*(p[i]-p[1]);  
  42.             }  
  43.             for(int i=2;i<=m;++i)  
  44.             {  
  45.                 s[i][n+1]=n;  
  46.                 for(int j=n;j>i;--j)  
  47.                 {  
  48.                     for(int k=s[i-1][j];k<=s[i][j+1];++k)  
  49.                     {  
  50.                         int tmp=dp[i-1][k]+(p[j]-p[k+1])*(p[j]-p[k+1]);  
  51.                         if(tmp<dp[i][j])  
  52.                         {  
  53.                             dp[i][j]=tmp;  
  54.                             s[i][j]=k;  
  55.                         }  
  56.                     }  
  57.                 }  
  58.             }  
  59.             printf("Case %d: %d\n",c++,dp[m][n]);  
  60.         }  
  61.     }  
  62.     return 0;  
  63. }  


 

4、hdu3516 题目大意：给你很多个点，让你用一棵树把所有点连在一齐，树只能往上跟右生长，求树的总长度最小。

 

[cpp] view
plaincopy

  1. #include <iostream>  
  2. #include <cstdio>  
  3. #include <cmath>  
  4. using namespace std;  
  5. #define min(a,b) ((a)<(b)?(a):(b))  
  6. #define inf 0x7ffffff  
  7. struct point{  
  8.     int x,y;  
  9. };  
  10. point p[1000];  
  11. int dp[1000][1000];  
  12. int s[1000][1000];  
  13. int w[1000][1000];  
  14. int getdis(point a,point b)  
  15. {  
  16.     return abs(a.x-b.x)+abs(a.y-b.y);  
  17. }  
  18. int main()  
  19. {  
  20.     int n;  
  21.     while(~scanf("%d",&n))  
  22.     {  
  23.         for(int i=1;i<=n;++i)  
  24.         {  
  25.             scanf("%d%d",&p[i].x,&p[i].y);  
  26.         }  
  27.         for(int i=1;i<n;++i)  
  28.         {  
  29.             for(int j=i+1;j<=n;++j)  
  30.             {  
  31.                 w[i][j]=getdis(p[i],p[j]);  
  32.             }  
  33.             s[i][i+1]=i;  
  34.             dp[i][i+1]=w[i][i+1];  
  35.         }  
  36.         for(int len=3;len<=n;++len)  
  37.         {  
  38.             for(int i=1;i<=n-len+1;++i)  
  39.             {  
  40.                 int j=i+len-1;  
  41.                 dp[i][j]=inf;   
  42.                 for(int k=s[i][j-1];k<=s[i+1][j];++k)  
  43.                 {  
  44.                     int tmp=dp[i][k]+dp[k+1][j]+w[i][j]+p[k].y-p[i].y+p[k+1].x-p[j].x;  
  45.                     //cout<<i<<' '<<j<<' '<<k<<' '<<tmp<<endl;  
  46.                     if(tmp<dp[i][j])  
  47.                     {  
  48.                         dp[i][j]=tmp;  
  49.                         s[i][j]=k;    
  50.                     }  
  51.                 }  
  52.             }  
  53.         }  
  54.         printf("%d\n",dp[1][n]);  
  55.     }  
  56.     return 0;  
  57. }  

5、hdu3506 题目大意：香蕉森林里一群猴子（n<=1000)围成一圈开会，会长给他们互相介绍，每个猴子需要时间a[i]。每次只能介绍相邻的两只猴子x和y认识，同时x所有认识的猴子和y所有认识的猴子也就相互认识了，代价为这两伙猴子认识的时间（a[i]）之和。求这群猴子都互相认识的最短时间。

这道题其实就是环形的石子合并问题，首先将环形dp转化为线性dp，对于长度为n的环，任意选取一点为起点，由起点开始得到一条长度为n的链，将前面n-1长度的链复制并转移到链的末端，相当于将两条同样的链首尾相接。这样环的任意一种单向遍历方式都可以在这个长度这为2n-1的链中实现。可见曾妞妞的《怎样实现环形动态规划问题》。

[cpp] view
plaincopy

  1. #include <cstdio>  
  2. #include <iostream>  
  3. #include <cstring>  
  4. using namespace std;  
  5. #define LL int  
  6. #define inf 1<<30  
  7. #define min(a,b) ((a)<(b)?(a):(b))  
  8. LL dp[2002][2002];  
  9. LL s[2002][2002];  
  10. LL p[2002];  
  11. LL w[2002][2002];  
  12. int main()  
  13. {  
  14.     int n;  
  15.     while(~scanf("%d",&n))  
  16.     {  
  17.   
  18.         for(int i=1;i<=n;++i)  
  19.         {  
  20.             scanf("%d",&p[i]);  
  21.             p[i+n]=p[i];  
  22.         }  
  23.         memset(s,0,sizeof(s));  
  24.         memset(w,0,sizeof(w));  
  25.         for(int i=1;i<2*n;++i)  
  26.         {  
  27.             for(int j=i;j<=i+n;++j)  
  28.             {  
  29.                 w[i][j]=w[i][j-1]+p[j];  
  30.             }  
  31.             s[i][i]=i;  
  32.             dp[i][i]=0;  
  33.         }  
  34.   
  35.         for(int len=2;len<=n;++len)  
  36.         {  
  37.             for(int i=1;i<=2*n-len+1;++i)  
  38.             {  
  39.                 int j=i+len-1;  
  40.                 dp[i][j]=inf;  
  41.                 for(int k=s[i][j-1];k<=s[i+1][j];++k)  
  42.                 {  
  43.                     LL tmp=dp[i][k]+dp[k+1][j]+w[i][j];  
  44.                     if(tmp<dp[i][j])  
  45.                     {  
  46.                         dp[i][j]=tmp;  
  47.                         s[i][j]=k;  
  48.                     }  
  49.                 }  
  50.             }  
  51.         }  
  52.           
  53.         LL ans=inf;  
  54.         for(int i=1;i<=n;++i)  
  55.         {  
  56.             ans=min(ans,dp[i][i+n-1]);  
  57.         }  
  58.         printf("%d\n",ans);  
  59.     }  
  60.     return 0;  
  61. }  
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞