CODE[VS] 1048 石子归并 - ChiLuManXi的部落格 - 博客频道 - CSDN.NET

CODE[VS] 1048 石子归并 - ChiLuManXi的部落格 - 博客频道 - CSDN.NET

有n堆石子排成一列，每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子，一次合并的代价为两堆石子的重量和w[i]+w[i+1]。问安排怎样的合并顺序，能够使得总合并代价达到最小。

http://lixinzhang.github.io/qu-jian-xing-dp.html
区间形DP特征：

F[i][j]=F[i][k]+F[k+1][j]+CostFunction(i,j)

设状态为F[i][j]，表示第i堆到第j堆石子合并之后的最小分值，那么其上一状态一定是由两个子堆合并而来，那么枚举中间分割位置k为决策状态,因此状态转移方程：

F[i][j]=F[i][k]+F[k+1][j]+sum(i,j)

其中sum(i,j)为两个自堆合并时，所产生的分值。

此类DP，先计算小区间，然后再通过小区间迭代得到大区间的值。

同类型的一道面试题

说有n个节点n条边组成一个圈，每个节点上面有一个数，边上有一个+或*，如果消掉某条边，其相邻两个节点就用这个运算符合并。这样一路消边到底，问用什么过程能让最后得到的数最大。

对于这个题目,是一个典型的区间型DP,是一道比较经典的题目,这道题我们写出的动态DP方程是这样的:

dp[i][j] = min{dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1]}, i <= k < j (i !+ j)

          =  0 (i = j)

这里的i到j是指i到j所需要的最小的代价.

我们还要借助一个额外的数组sum来记录从i到j的大小,这个时候我们只需要记录从1到最后n的每一段的代价,最后进行相减就可以求出i到j的重量.

每当合成了一堆以后我们就要减少我们总遍历的个数.即每合并一次总数减1.

我们只需要从左边开始遍历即可.就可以得到所有的情况:

http://blog.csdn.net/kingzone_2008/article/details/12361327

int main()
{
    cin >> n;
    for(int i=1; i<=n; i++)
    {
      cin >> w[i];
      sum[i] = sum[i-1] + w[i];
    }
    for(int len=2; len<=n; len++)
    {
      for(int i=1; i<=n-len+1; i++)
      {
        int j=i+len-1;
        minV = 0x7fffffff;
        for(int k=i; k<j; k++)
        {
          if(minV > dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1])
            minV = dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
        }
        dp[i][j] = minV;
      }
    }
    cout << dp[1][n];
    return 0; 

}
http://lixinzhang.github.io/qu-jian-xing-dp.html

int mergeStore(int F[][101], int store[], int sum[][101], int n){
    //dynamic programming
    //F[i][j] = F[i][k] + F[k+1][j] + sum(i,j);
    //F[i][j]表示将第    
    //init
    for(int i=0; i<n; i++) F[i][i] = 0;
    for(int step = 1; step < n ; step++)
    {
        for(int i=0; i<n-step; i++){
            int j = i+step;
            F[i][j] = INT_MAX;
            for(int k=i; k<j; k++){
                F[i][j] = min(F[i][k] + F[k+1][j] + sum[i][j], F[i][j]);
            }
        }
    }
    return F[0][n-1];
}
void initSum(int sum[][101], int store[], int n){
    for(int i=0; i<n; i++){
        sum[i][i] = store[i];
        for(int j=i+1; j<n; j++){
            sum[i][j] = sum[i][j-1] + store[j];
        }
    }
}
int main(){
    int n, tmp;
    int store[101];
    int F[101][101];
    int sum[101][101];
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> tmp;
        store[i] = tmp;
    }
    //init sum
    initSum(sum, store, n);
    cout<<mergeStore(F, store, sum, n)<<endl;

    return 0;
}

Read full article from CODE[VS] 1048 石子归并 - ChiLuManXi的部落格 - 博客频道 - CSDN.NET