朴素的DP石子归并
原题：https://codevs.cn/problem/1048/
1048 石子归并
题目描述 Description
有n堆石子排成一列，每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子，一次合并的代价为两堆石子的重量和w[i]+w[i+1]。问安排怎样的合并顺序，能够使得总合并代价达到最小。
输入描述 Input Description
第一行一个整数n（n<=100）
第二行n个整数w1,w2...wn (wi <= 100)
输出描述 Output Description
一个整数表示最小合并代价
样例输入 Sample Input
4
4 1 1 4
样例输出 Sample Output
18
个人解法：
作为经典的区间DP，就不再说多。
在这里我的DP数组f[i,j]表示从第i堆到第j堆的最小代价。
代码如下：
uses math;//懒人不打min，调用数学函数库……
var
w,f:array[0..100,0..100] of longint;
i,j,k,n:longint;
begin
read(n);
for i:=1 to n do
read(w[i,i]);
for i:=1 to n do
for j:=i+1 to n do
w[i,j]:=w[i,j-1]+w[j,j];//初始化，w[i,j]表示第i堆到第j堆的所有石子数
for i:=n-1 downto 1 do//从后往前推
for j:=i+1 to n do
begin
f[i,j]:=maxlongint;//很重要
for k:=i to j-1 do
f[i,j]:=min(f[i,k]+f[k+1,j]+w[i,j],f[i,j]);//DP方程
end;
writeln(f[1,n]);
end.
我们知道其实这一题还有另一种做法。
在上述代码中：
f[i,j]表示从第i堆到第j堆的最小代价，所以动态转移方程为
f[i,j]=min(f[i,k]+f[k+1,j]+w[i,j]),其中1<=i<=n-1，i+1<=j<=n，i<=k<=j-1。
最后的答案为f[1,n]，并且我们要先把左端点i从后往前枚举，再把右端点j从前往后枚举，这两个东西不能逆序枚举。至于k怎么枚举，开心就好。
但是如果我们不开心，不喜欢downto，怎么办呢？
我们发现，之所以从n-1开始往前downto，就是因为在我们的状态转移方程中，我们在求f[i,j]时只知道f[i,k]，并不知道f[k+1,j]（因为我们的左端点还没有求到k）。所以如果我们把左端点i从n-1开始枚举，我们就已经知道f[i,k]和f[k+1,j]了，所以这个时候的DP就是正确的。
于是我们就想到DP的无后效性（为什么和无后效性扯上了关系……）。因为我们在求的当前状态是由上一状态推出来的，那么我们总应该要知道上一状态的所有决策所得到的最优答案。
那么我们就发现了，我们可以枚举区间的长度。
因为求当前长度，需要用比它小的长度的区间来操作。这个时候，我们顺着for，DP就是正确的了。
状态转移方程与第一种方法一样，但是在DP的时候有点小不同。至于具体方法，下一个题就是一个很好的例子。
原题：https://codevs.cn/problem/2102/
2102 石子归并 2
题目描述 Description
在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.
输入描述 Input Description
数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.
输出描述 Output Description
输出共2行,第1行为最小得分,第2行为最大得分.
样例输入 Sample Input
4
4 4 5 9
样例输出 Sample Output
43
54
个人解法：
看到原题时间限制10s……（大雾）估计是打错了，因为1s是绰绰有余的，而且，我的代码只需1ms（我认为应该是数据弱），应该是还有比我程序更快的。
这也是一个经典的区间DP。
对于环状的区间，我们枚举长度也许就会更好。
首先我们从小到大枚举长度，接下来我们从左到右枚举左端点，之后我们就可以计算出右端点。之后再for一遍求最优解。
当然还有一点数据处理。我们可以用两倍的数组来储存起点为i顺时针长度共j-i+1的区间。
代码如下：
uses math;//懒人调用的数学函数库。
var
n,i,j,k,l,minn,maxx:longint;
f1,f2:array[0..100,0..100] of longint;
s,w:array[0..200] of longint;
function num(l,r:longint):longint;//计算l到r的所有石子数
begin
exit(s[r]-s[l-1]);
end;
begin
read(n);
for i:=1 to n do
read(w[i]);
for i:=1 to n do
s[i]:=s[i-1]+w[i];
for i:=n+1 to 2*n do
s[i]:=s[i-1]+w[i-n];//处理起点为i顺时针长度共j-i+1的区间。
for l:=2 to n do
for i:=1 to 2*n-l+1 do
begin
j:=i+l-1;
f1[i,j]:=maxlongint;
for k:=i to j-1 do
begin
f2[i,j]:=max(f2[i,j],f2[i,k]+f2[k+1,j]+num(i,j));//两次DP
f1[i,j]:=min(f1[i,j],f1[i,k]+f1[k+1,j]+num(i,j));
end;
end;
minn:=maxlongint;
for i:=1 to n do
begin
maxx:=max(maxx,f2[i,i+n-1]);
minn:=min(minn,f1[i,i+n-1]);//不一定是第1堆开始最优
end;
writeln(minn);
writeln(maxx);
end.
原题：https://codevs.cn/problem/3002/
3002 石子归并 3
题目描述 Description
有n堆石子排成一列，每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子，一次合并的代价为两堆石子的重量和w[i]+w[i+1]。问安排怎样的合并顺序，能够使得总合并代价达到最小。
输入描述 Input Description
第一行一个整数n（n<=3000）
第二行n个整数w1,w2...wn (wi <= 3000)
输出描述 Output Description
一个整数表示最小合并代价
样例输入 Sample Input
4
4 1 1 4
样例输出 Sample Output
18
个人解法：
诶？这不是和石子归并1一样的吗？
只是数据范围大了些嘛……
先不管那么多，把石子归并1的源码版上去，看看多少分。
多少分呢，50分。
那怎么办呢？
我们很神奇地发现这是区间DP。
处理区间DP时间优化，我们有没有想到神奇的四边形不等式？
于是我们就惊奇地发现这就是朴素的四边形不等式练习题。
至于四边形不等式……可以去看看：
同样，f[i,j]表示第i堆到第j堆的最小代价。
所以，我们就用s[i,j]表示f[i,j]决策时的k的值。
也就是说，我们在求f[i,j]的时候，是从i到j枚举k，最后找到一个k使得f[i,j]最小。
那么s[i,j]的值就是k。
根据四边形不等式，我们就可以得出：
s[i,j-1]<=s[i,j]<=s[i+1,j]。
所以现在我们就只需要从s[i,j-1]开始枚举k，到s[i+1,j]停止。
接下来我们就考虑怎样DP。
我们发现，我们要用到这一个优化，如果最先枚举左端点i，那么我们就要知道s[i+1,j]，所以我们就应该从n-1开始往前枚举i。
我们还可以枚举长度，因为我们要知道的s[i,j-1]与s[i+1,j]长度均比s[i,j]小。
这两种方法在石子归并1和2都已经说过，这里就不再赘述。
于是我们就把时间复杂度O(n^3)降到了O(n^2)。
代码如下：
uses math;//懒人不想打min函数
var
w:array[-2..3020] of int64;
f,s:array[-2..3020,-2..3020] of int64;//f与s均如解析
i,j,k,n,l:longint;
begin
read(n);
for i:=1 to n do
begin
read(j);
w[i]:=w[i-1]+j;
end;
fillchar(f,sizeof(f),127);
for i:=1 to n do
begin
s[i,i]:=i;//这里又是懒人思想……在我们求s[i,j]的时候需要用s[i,j-1]。第一次我们需要求的是f[i,i+1]。所以为了少写if，就把初始化变成了这玩意。
f[i,i]:=0;
end;
for l:=2 to n do
for i:=1 to n-l+1 do
begin
j:=l+i-1;
for k:=s[i,j-1] to s[i+1,j] do
begin
if f[i,j]>f[i,k]+f[k+1,j]+w[j]-w[i-1] then
begin
f[i,j]:=f[i,k]+f[k+1,j]+w[j]-w[i-1];
s[i,j]:=k;//决策时k的值，而且，这里是顺序枚举，可以保证在最优决策数量>1的时候取到最大的k，从而进一步缩小下一次k的枚举范围。
end;
end;
end;
writeln(f[1,n]);
end.
三个石子归并都over了。所谓数据越大越是激发思考者的大脑。三个石子归并一完，不写题解不知道，一写题解才发现原来区间DP还有如此多的解法。所谓经典，以此为称。
DP路上，希望与你们共同进步。