区间DP主要思想是先在小区间取得最优解，然后小区间合并时更新大区间的最优解。
基本代码：
//mst(dp,0) 初始化DP数组
for(int i=;i<=n;i++)
{
dp[i][i]=初始值
}
for(int len=;len<=n;len++) //区间长度
for(int i=;i<=n;i++) //枚举起点
{
int j=i+len-; //区间终点
if(j>n) break; //越界结束
for(int k=i;k<j;k++) //枚举分割点，构造状态转移方程
{
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+][j]+w[i][j]);
}
}
【题目描述】
N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。
例如： 1 2 3 4，有不少合并方法
1 2 3 4 => 3 3 4(3) => 6 4(9) => 10(19)
1 2 3 4 => 1 5 4(5) => 1 9(14) => 10(24)
1 2 3 4 => 1 2 7(7) => 3 7(10) => 10(20)
Sample Input
4
1
2
3
4
Sample Output
19
预处理出区间和，然后枚举每个长度的区间和断点，转移即可。
f[i][j] = min(f[i][j], f[i][k]+f[k+1][j]+sum[j]-sum[i-1])
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int maxn = + ;
#define INF 0x3f3f3f3f int main()
{
int n;
scanf("%d", &n);
int sum[maxn];
int f[maxn][maxn];
memset(f, , sizeof(f)); for (int i = ; i <= n; i++)
{
int x;
scanf("%d", &x);
sum[i] = sum[i-]+x;
} for (int len = ; len <= n; len++)
{
for (int i = ; i <= n; i++)
{
int j = i+len-;
f[i][j] = INF;
for (int k = i; k < j; k++)
f[i][j] = min(f[i][j], f[i][k]+f[k+][j] + sum[j] - sum[i-]);
}
} printf("%d\n", f[][n]);
}
题意：
有一根长度为 n 的木棍，m 个可以切开的位置。
如果把一个长木棍切成两根短木棍，那么花费就是那根长木棍的长度。
求把这根木棍按照 m 个切点全部切开的最小花费。
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define maxn 100 + 100
#define INF 0x3f3f3f3f int main()
{
int n, m;
while(scanf("%d%d", &n, &m) == && n)
{
int x[maxn];
for (int i = ; i <= m; i++)
scanf("%d", &x[i]); x[] = , x[m+] = n; int f[maxn][maxn];
for (int i = ; i <= m+; i++)
{
for (int j = ; j <= m+; j++)
f[i][j] = INF;
f[i][i+] = ;
} for (int len = ; len <= m+; len++)
for (int i = ; i+len <= m+; i++)
{
int j = i+len;
for (int k = i+; k < j; k++)
f[i][j] = min(f[i][k] + f[k][j] + x[j] - x[i], f[i][j]);
} printf("The minimum cutting is %d.\n", f[][m+]);
}
}
有一串首位相连的环形能量珠项链，每个能量珠由头部和尾部组成。相邻的能量珠必定是某一个的头部 = 另一个的尾部。
可以把两个相邻的能量珠（a,b）（b,c）合成一个新的能量珠（a, c），并且释放 a * b * c的能量。
操作这串能量珠能够获得的最大的总能量是多少？
样例中，四个能量珠分别为(2, 3) (3, 5) (5, 10) (10, 2)
对于环形区间，我们只要把它展开成线形区间进行DP，然后取 dp[i, i+n-1] 中的最大值就可以了。
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std; #define maxn 200 + 100
#define INF 0x3f3f3f3f int main()
{
int n;
while(~scanf("%d", &n))
{
int a[maxn], sum[maxn], f[maxn][maxn];
memset(sum, , sizeof(sum)); for (int i = ; i <= n; i++)
{
scanf("%d", &a[i]);
a[n+i] = a[i];
}
a[*n+] = a[]; for (int i = ; i <= *n; i++)
for (int j = i; j <= *n; j++)
f[i][j] = ; for (int len = ; len <= *n; len++)
for (int i = ; i+len- <= *n; i++)
{
int j = i+len-;
for (int k = i; k < j; k++)
f[i][j] = max(f[i][j], f[i][k] + f[k+][j] + a[i]*a[k+]*a[j+]);
} int ans = ;
for (int i = ; i <= n; i++)
ans = max(ans, f[i][i+n-]); printf("%d\n", ans); } }
也是普通的环形区间DP，拆环为链。
然而这样过不了的。因为数据范围是2000，n^3的DP会TLE。
所以需要用平行四边形优化。
这个玩意我还没有看懂，只是拿过来用。以后慢慢理解。
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std; #define maxn 2000 + 100
#define INF 0x3f3f3f3f int main()
{
int n;
while(~scanf("%d", &n))
{
int a[maxn], sum[maxn], f[maxn][maxn], s[maxn][maxn];
memset(sum, , sizeof(sum)); for (int i = ; i <= n; i++)
{
scanf("%d", &a[i]);
a[n+i] = a[i];
} for (int i = ; i <= *n; i++)
sum[i] = sum[i-] + a[i]; for (int i = ; i <= *n; i++)
{
f[i][i] = ;
s[i][i] = i; //这里的s数组也要初始化
for (int j = i+; j <= *n; j++)
f[i][j] = INF;
} for (int len = ; len <= *n; len++)
for (int i = ; i+len- <= *n; i++)
{
int j = i+len-;
for (int k = s[i][j-]; k <= s[i+][j]; k++) //单调性枚举
{
int tmp = f[i][k] + f[k+][j] + sum[j] - sum[i-];
if (tmp < f[i][j])
{
f[i][j] = tmp;
s[i][j] = k;
}
}
} int ans = INF;
for (int i = ; i <= n; i++)
ans = min(ans, f[i][i+n-]); printf("%d\n", ans); } }