区间DP入门——石子合并问题_stone merge dp

石子合并问题是最经典的DP问题。首先它有如下3种题型：

(1)有N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动任意的2堆石子合并，合并花费为新合成的一堆石子的数量。求将这N堆石子合并成一堆的总花费最小（或最大）。

分析：当然这种情况是最简单的情况，合并的是任意两堆，直接贪心即可，每次选择最小的两堆合并。本问题实际上就是哈夫曼的变形。

(2)有N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动相邻的2堆石子合并，合并花费为新合成的一堆石子的数量。求将这N堆石子合并成一堆的总花费最小（或最大）。

可以看出，上面的(2)(3)问题的时间复杂度都是O(n^3)，由于过程满足平行四边形法则，故可以进一步优化到O(n^2)。

对于石子合并问题，有一个最好的算法，那就是GarsiaWachs算法。时间复杂度为O(n^2)。

它的步骤如下：

设序列是stone[]，从左往右，找一个满足stone[k-1] <= stone[k+1]的k，找到后合并stone[k]和stone[k-1]，再从当前位置开始向左找最大的j，使其满足stone[j] > stone[k]+stone[k-1]，插到j的后面就行。一直重复，直到只剩下一堆石子就可以了。在这个过程中，可以假设stone[-1]和stone[n]是正无穷的。

本人的：

/*


用T[i][j]代表从i到j连续的所有石堆合并后的整体 i<=j
dp[i][j]代表形成T[i][j]所需要的最小花费 
i==j时：
dp[i][j] = 0;因为不需要合并 因为dp数组是全局所以可以省去
i<j时：
T[i][j]肯定是由某两个【相邻】子堆组合而成 假设这个分界点是k,那么这两个子堆是T[i,k]和T[k+1][j],其中i<=k<j;
T[i][j]最小总花费是由两部分组成：
1) T[i][k]和T[k+1][j]各自的最小花费之和所形成的集合里的最小值(用k=i...j-1循环求最小和)
2) 组合T[i,k]和T[k+1][j]成为T[i][j]的动作需要的花费，其实就是这两个堆的总重量，也就是T[i][j]的重量,记录为w[i][j]
得到那么得到方程:dp[i][j] = min{dp[i][k]+dp[k+1][j]}+w[i][j];
w[i][j]一种简便求法:
我们使用w[i]来存储w[1]~w[i]所有堆重量之和
那么w[i][j]就是 w[j] - w[i-1];
自底向上构造:
注意到
所有长度为2的T[i][j]需要使用所有长度为1的T[i][j];
所有长度为3的T[i][j]需要使用所有长度为1/2的T[i][j];
所有长度为4的T[i][j]需要使用所有长度为1/2/3/4的T[i][j];
.....
所有长度为n的T[i][j]需要使用所有长度为1/2/3.....n-2/n-1的T[i][j];
用l代表长度,l->2~(n);i,j代表某一段的左右坐标
dp[i][j]代表形成T[i][j]所需要的最小花费 原问题dp[1][n]
复杂度O(n^3)
*/

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
int w[105];
int dp[105][105];
int main()
{
int n;
cin>>n;
for(int i= 1;i<=n;i++)
{
cin>>w[i];
w[i]+=w[i-1];
}
for(int l = 2;l<=n;l++)
for(int i= 1;i<n;i++)
{
int j = i+l-1;
int amin = INT_MAX;
for(int k = i;k<j;k++)
{
amin = min(amin,dp[i][k]+dp[k+1][j]);
}
dp[i][j] = amin + w[j]-w[i-1];\
}
cout<<dp[1][n]<<endl;
}
/**
#include<iostream>
using namespace std;
int N;//石子的堆数
int num[100]={0};//每堆石子个数
int sum(int begin,int n)
{
     int total=0;
     for (int i=begin;i<=begin+n-1;i++)
     {   if(i==N)
              total=total+num[N];//取代num[0]
         else
              total=total+num[i%N];
     }
     return total;
}
int stone_merge()
{
       int score[100][100];//score[i][j]:从第i堆石子开始的j堆石子合并后最小得分
       int n,i,k,temp;
       for (i=1;i<=N;i++)
           score[i][1]=0;//一堆石子，合并得分为0
       //num[0]=num[N];//重要：sum()函数中i=N时,取num[0]
       for (n=2;n<=N;n++)//合并的石子的堆数
       {
           for (i=1;i<=N;i++)//合并起始位置
           {
               score[i][n]=score[i][1]+score[(i+1-1)%N+1][n-1];
               for (k=2;k<=n-1;k++)//截断位置
               {
                  temp=score[i][k]+score[(i+k-1)%N+1][n-k];
                  if(temp <score[i][n])
                        score[i][n] = temp;//从第i开始的k堆是：第i+0堆到第(i+k-1)%N堆
               }
               score[i][n]+=sum(i,n);
           }
       }
       int min=2147483647;
       for (i=1;i<=N;i++)
       {    if (min>score[i][N])
                  min=score[i][N];//取从第i堆开始的N堆的最小者
       }
       return min;
}
int main()
{
       int min_count=0;
       cin>>N;//石子的堆数
           for (int i=1;i<=N;i++)
               cin>>num[i];//每堆石子的数量//从1开始,num[0]不用
           min_count=stone_merge();
           cout<<min_count<<endl;
       return 0;
}
**/
 
 
 
 
#include<stdio.h>
int N;//最多100堆石子:N=100
int num[200]={0};
int max=-0x3f3f3f3f;
int stone_merge()
{
    int score[200][101]={0};//l[i][j]:从第i堆石子起合并n堆石子的最小得分
    int score2[200][101]={0};
    int n,i,k,temp,t2;
    for(i=0;i<2*N;i++)
        {
            score[i][1]=0;//一堆石子合并得分为0
            score2[i][1]=0;
        }
    for(n=2;n<=N;n++)//合并n堆石子
    {
        for(i=0;i<=2*N-n;i++)//从第i对开始合并(有一次重复运算，但省去了循环取数，简化了程序)
        {
            score[i][n]=score[i][1]+score[i+1][n-1];
            score2[i][n]=score2[i][1]+score2[i+1][n-1];
            for(k=2;k<n;k++)//划分
            {   temp=score[i][k]+score[k+i][n-k];
                t2=score2[i][k]+score2[k+i][n-k];
                if(temp<score[i][n])
                    score[i][n]=temp;//取(i,n)划分两部分的得分
                    if(t2>score2[i][n])
                        score2[i][n]=t2;
            }
            for(k=i;k<i+n;k++)
                {
                    score[i][n]+=num[k];//加上此次合并得分
                    score2[i][n]+=num[k];
                }
        }
    }
    int min=2147483647;//int(4位)最大值为2147483647
    for(i=0;i<N;i++)
    {
        if(score[i][N]<min)
            min=score[i][N];//从第i堆开始取N堆石子，的最小合并得分
            if(score2[i][N]>max)
                max=score2[i][N];
    }
    return min;
}
 
 
int main()
{
    int min_count;
    scanf("%d",&N);//N堆石子
        for(int i=0;i<N;i++)
            scanf("%d",&num[i]);//每堆石子的数量
        for(int i=N;i<2*N;i++)
            num[i]=num[i-N];//复制一倍，化简环形计算（N堆石子是围成一个环的）
        if(N==1)    min_count=0;
        else if(N==2)    min_count=num[0]+num[1];
        else    min_count=stone_merge();
        printf("%d\n",min_count);
        printf("%d\n",max);
    return 0;
}