HDU 2829 Lawrence(四边形优化DP O（n^2）)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2829

题目大意：有一段铁路有n个站，每个站可以往其他站运送粮草，现在要炸掉m条路使得粮草补给最小，粮草补给的公式是将每个站能收到的粮草的总和。

4----5-----1-----2

粮草总和为4*5 + 4*1 + 4*2 + 5*1 + 5*2 + 1*2 = 49.

4----5 1-----2

粮草总和为4*5 + 1*2 = 22.

4 5-----1------2

粮草总和为5*1 + 5*2 + 1*2 = 17.

解题思路：参考，状态转移方程为dp[i][j]=min{dp[k][j-1]+cost[k+1][i]}(k<i)，若cost[i][j]满足凸四边形不等式，则可以用四边形优化。

　　　　　这里我们有一个定理：cost为凸当且仅当 cost[i][j] + cost[i+1][j+1] <= cost[i+1][j] + cost[i][j+1]。

　　　　　我们可以把原式cost[i][j] + cost[i'][j'] <= cost[i][j'] + cost[i'][j]变为cost[i + 1][j + 1] - cost[i + 1][j] <= cost[i][j + 1] - cost[i][j]，然后固定j变化i，看coat[i][j+1] - cost[i][j]是关于i递增还是递减，如果是递减，则cost为凸。

　　　　　一般如果不能直接看出来，可以进行打表。此题cost[i][j]满足该定理，于是可以用四边形优化将复杂度降至O（n^2）。

　　　　　注意：这里的是s[i][j]处理跟石子归并时不一样，还有i是倒着来的，不是正着的。

代码：

 #include<iostream>

 #include<cstring>

 using namespace std;

 typedef long long LL;

 const int N=1e3+;

 const long long INF=0x3f3f3f3f;

 LL sum[N],dp[N][N],cost[N][N],s[N][N];//s[i][j]记录dp[i][j]的最优切割点 

 int main(){

     int n,m;

     while(~scanf("%d%d",&n,&m)){

         if(n==&&m==)

             break;

         memset(cost,,sizeof(cost));

         memset(dp,INF,sizeof(dp));

         for(int i=;i<=n;i++){

             scanf("%lld",&sum[i]);

             sum[i]+=sum[i-];

             s[i][]=;

         }

         //计算cost[i][j]

         for(int i=;i<=n;i++){

             for(int j=;j<i;j++){

                 cost[][i]+=(sum[j]-sum[j-])*(sum[i]-sum[j]);

             }

             dp[i][]=cost[][i];

         }

         for(int k=;k<=n;k++){

             for(int i=k+;i<=n;i++){

                 cost[k][i]=cost[][i]-cost[][k-]-sum[k-]*(sum[i]-sum[k-]);

             }

         }

         //j为轰炸次数,当i = 1或者j = n时为边界对s的处理就是为了处理这些边界

         for(int j=;j<=m;j++){

             s[n+][j]=n-;

             for(int i=n;i>=j;i--){

                 for(int k=s[i][j-];k<=s[i+][j];k++){

                     LL tmp=dp[k][j-]+cost[k+][i];

                     if(tmp<dp[i][j]){

                         dp[i][j]=tmp;

                         s[i][j]=k;

                     }

                 }

             }

         }

         printf("%lld\n",dp[n][m]);

     }

     return ;

 }

巴特西

HDU 2829 Lawrence(四边形优化DP O（n^2）)

最新文章

热门文章