石子合并——区间dp

282. 石子合并 - AcWing题库

所有的区间dp问题枚举时，第一维通常是枚举区间长度，并且一般 len = 1 时用来初始化，枚举从 len = 2 开始；第二维枚举起点 i （右端点 j 自动获得，j = i + len - 1）

这就是典型的区间dp问题。因为求的是1到n的代价最小值，所以我们可以先一般化，最后再得出特殊的1到n的代价。

状态表示：区间【i，j】的代价总和的最小值。

对于区间【i，j】，我们可以细化分为【i，k】与【k+1，j】的合并项，其中k的范围是大于等于i，小于j。

状态计算：
1.如果i==j，则f [ i , j ] 初始化为0

2.如果i！= j，则f [ i , j ] = min( f [ i ] [ k ] + f [k  +1  ][ j  ] + s[ j ] - s [ i  -1 ] )

　　其中s[ j ] - s [ i  -1 ]是从i到j的代价前缀和相减得到的最后一次两堆石子合并的代价和

1 #include
2 using namespace std;
3 const int N=350;
4 int a[N],f[N][N],s[N];
5
6 int main()
7 {
8 int n;scanf("%d",&n);
9 for(int i=1;i<=n;i++)
10 {
11 scanf("%d",&a[i]);
12 s[i]=s[i-1]+a[i];
13 }
14
15 for(int len=1;len<=n;len++)
16 {
17 for(int i=1;i+len-1<=n;i++)
18 {
19 int j=i+len-1;
20 if(i==j) //初始化
21 {
22 f[i][j]=0;
23 continue;
24 }
25 f[i][j]=0x3f3f3f3f; //初始化
26 for(int k=i;k)
27 {
28 f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
29 }
30 }
31 }
32
33 printf("%d\n",f[1][n]);
34
35 return 0;
36 }

View Code