DLKKILL

DLKKILL's world

51nod-1021-石子归并 (区间DP,四边形优化)

题目链接:1021 石子归并

题目大意:

N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。

Input

第1行:N(2 <= N <= 100)
第2 - N + 1:N堆石子的数量(1 <= A[i] <= 10000)

题目分析:

经典的区间DP问题,

有递推公式:

dp[i][j]=0 ( i-j);

dp[i][j]=min(dp[i][k],dp[k+1][j])+sum[i][j] i!=j

该公式可以进行四边形优化:

当函数w(i,j)满足 w(a,c)+w(b,d) <= w(b,c)+w(a,d) 且a<=b< c <=d 时,我们称w(i,j)满足四边形不等式。。

当函数w(i, j)满足w(i', j) <= w(i, j'); i <= i' < j <= j' 时,称w关于关于区间包含关系单 调。

s(i, j)=k是指m(i, j)这个状态的最优决策。

所以,最终可以将复炸度优化到n2

给出代码:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const int maxn=50000+10;
const int inf=0x3f3f3f3f;
int nums[maxn];
int sums[maxn];
int dp[maxn][maxn];
int s[maxn][maxn];
int n;
int main()
{
   while(cin>>n)
   {
       memset(sums,0,sizeof(sums));
       for(int i=0;i<n;i++)
        {
            cin>>nums[i];
            sums[i]+=nums[i];
            if(i!=0)
                sums[i]+=sums[i-1];
            s[i][i]=i;
        }
       memset(dp,inf,sizeof(dp));
       for(int i=0;i<n;i++)
            dp[i][i]=0;
       for(int l=1;l<=n-1;l++)
       {
           for(int i=0;i+l<n;i++)
           {
               int j=i+l;
               //cout<<i<<" "<<j<<endl;
               for(int k=s[i][j-1];k<=s[i+1][j];k++)
                {
                    //dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sums[j]-sums[i]+nums[i]);
                    if(dp[i][j]>dp[i][k]+dp[k+1][j]+sums[j]-sums[i]+nums[i])
                    {
                        s[i][j]=k;
                        dp[i][j]=dp[i][k]+dp[k+1][j]+sums[j]-sums[i]+nums[i];
                    }
                    //cout<<dp[i][j]<<" "<<i<<" "<<k+1<<" "<<j<<" "<<dp[i][k]<<" "<<dp[k+1][j]<<endl;
                }
           }
       }
       cout<<dp[0][n-1]<<endl;
   }
   return 0;
}

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注