合并石子题解

题目描述在一圆形操场四周摆放N堆石子 , 现要将石子有次序地合并成一堆.规定每次只能选相临的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的代价。
编一程序,由文件读入堆数N及每堆石子数,
选择一种合并石子的方案,使得做N-1次合并,代价的总和最少
输入第1行：1个整数n(1<=n<=1000)，表示石子的数量
第2行：n个用空格分开的整数，每个整数均小于10000，表示各堆石子的数量。
输出 【合并石子】输入仅一行：1个整数，表示最小的归并代价
样例输入

3 13 7 8

样例输出

43 49

题解此题仔细想想，石子是不是圆形都一样，都可理解为排成一列，所以可以按输入顺序编号。合并n-1次，即把这些石子合并为一堆。现在就好做一些了
设ｄｐ［ｉ］［ｊ］表示合并（合并为一堆，下文同）第ｉ堆石子到第ｊ堆石子的最小花费，则：

文章图片
（ｉ＜＝ｋ＜＝ｊ）
其中，w［ｉ］［ｊ］表示第ｉ堆石子到第ｊ堆石子的石子总个数。上述公式可这样理解：合并第ｉ堆到第ｋ堆的最小花费，加上合并第ｋ＋１堆到第ｊ堆的最小花费，还要将这两堆合并成一堆，合并这两堆的花费是ｗ［ｉ］［ｊ］，所以还要加上
ｗ［ｉ］［ｊ］。
由于ｋ＞＝ｉ，所以ｉ要从ｎ循环到１，这样ｄｐ［ｋ＋１］［ｊ］才有值；ｊ就没关系了，ｉ～ｎ和ｎ～ｉ都可以
细节处理：
ｄｐ［ｉ］［ｉ］＝０，ｗ［ｉ］［ｊ］可以用前缀和算，节省时间
优化
设ｓ［ｉ］［ｊ］为ｄｐ［ｉ］［ｊ］的最优的ｋ，即
dp[i][j]=dp[i][s[i][j]]+dp[s[i][j]+1][j]+w[i][j]
这个ｓ［ｉ］［ｊ］的求法就是朴素算法，只不过多了记录。但这个ｓ［ｉ］［ｊ］的取值范围是可以确定的，即：
ｓ［ｉ］［ｊ－１］＜＝ｓ［ｉ］［ｊ］＜＝ｓ［ｉ＋１］［ｊ］
这个东西证明起来也不难，用数学即可，可以自己思考。当然，也可以先记录，不用，输出来看看满不满足这个规律，满足就可以这样做。实际很多这类的ｄｐ都有这样的规律，可以节省时间。但要这样处理一下：

if (s[i][j - 1] == 0) s[i][j - 1] = i; if (s[i + 1][j] == 0) s[i + 1][j] = j;

这里相当于朴素算法（以后有值就减少了循环次数），所以要初始化清零。因为这里是ｓ［ｉ］［ｊ－１］，要让它尽可能有值，所以ｊ从ｉ循环到ｎ。
核心代码：

for(i = n; i >= 1; i--){ dp[i][i] = 0; for(j = i + 1; j <= n; j++){ if (s[i][j - 1] == 0) s[i][j - 1] = i; if (s[i + 1][j] == 0) s[i + 1][j] = j; for(k = s[i][j - 1]; k <= s[i + 1][j]; k++) if (dp[i][j] > dp[i][k] + dp[k + 1][j] + w[i][j]){ dp[i][j] = dp[i][k] + dp[k + 1][j] + w[i][j]; s[i][j] = k; } } }