51nod1021(区间dp)

题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1021

题意：中文题诶～

思路：区间dp

我们用num[i]存储前i个元素的和，用dp[i][j]存储合并从第i个到第j个元素的代价，那么有动态转移方程式为:

dp[i][j]=min(dp[i][j], dp[i][k]+dp[k+1][j]+num[j]-num[i-1])；

还有一个问题：如果我们直接枚举i, j的话有可能我们在计算dp[i][j]时dp[k+1][j]还没计算出来，这样我们自然不能得到正确答案咯．

其实我们只要换个思路就能解决这个问题啦，我们枚举len, 和i，len表示当前合并的区间长度为len，那么j＝ｉ+len-1．

这样就不会有上面的问题啦，因为区间i,k和区间k+1,j的长度一定小于区间i, j的长度，即在计算dp[i][j]之前我们已经计算出dp[i][k]和dp[k+1][j]啦．

代码：

 #include <bits/stdc++.h>

 #define MAXN 110

 using namespace std;

 int a[MAXN], num[MAXN], dp[MAXN][MAXN]; //***dp[i][j]存储第i堆到第j堆的合并代价

 const int inf=0x3f3f3f3f;

 int main(void){

     int n, ans=;

     cin >> n;

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

         cin >> a[i];

         num[i]=num[i-]+a[i];

     }

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

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

             int j=i+len-;  //***这里要注意j可能会大于n

             if(j<=n){

                 dp[i][j]=inf;

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

                     dp[i][j]=min(dp[i][j], dp[i][k]+dp[k+][j]+num[j]-num[i-]);

                 }

             }

         }

     }

     cout << dp[][n] << endl;

 }

巴特西

51nod1021(区间dp)

最新文章

热门文章