区间DP，对于每段小区间，它的最优值是由更小的区间的最优值得出的，由此往下划分，直到单个元素，由他们的组合合并得出最优解。
484感觉这个有套路
首先要分析题目，找最优子区间，分清取左区间边界，还是右区间边界
总结了一个区间的套路板子，这个过程也可以用递归实现
for (int l = st; l < len-(); l++) //l：区间长度
for (int i = st; l < len-l+1; l++) // i:区间起点
{
int j = i+l-1; //j: 区间终点
for (int k = i; k < j; k++) // 状态转移过程
dp[i][j] = MAX/MIN(f[i][j], f[i][k]+f[k+1][j]+w[i][j]);
//f[i , j]= max{f[ i,k]+ f[k+1,j]+ w[i,j] }
// 这个484很像最短路/最小生成树的松弛过程
}
下面来看几个栗子吧
POJ1651（石子合并类）
大致题意就是给你一个数列，从非头尾的数字中取数字，求这些数字与左右数字乘积之和，求最小和。很明显的石子合并问题，求每个区间最小值，合并得出区间最小值。
#define LL long long
#define INF 1e9
const int N = 101;
LL dp[N][N], p[N];
int vis[N];
int main()
{
int n;
scanf("%d", &n);
int minn=-INF, cur;
for (int i = 1; i <= n; i++)
scanf("%lld", &p[i]);
for (int m = 2; m <= n-1; m++) //可取区间[2, n-1]
for (int i = 2; i <= n-m+1; i++) //区间起点，第二个2数字
{
int j = m+i-1; //区间终点，最小组合区间长度3
dp[i][j] = INF;
for (int k = i; k < j; k++)
dp[i][j] = min(dp[i][j], dp[i][k] + p[i-1]*p[j]*p[k] + dp[k+1][j]);
}
printf("%I64d\n", dp[2][n]);
}
POJ2955（括号合并问题）
const int N = 120;
int dp[N][N];
string s;
int main()
{
while(cin >> s)
{
if(s == "end") break;
CLR(dp);
int len = s.size();
for(int i = 1; i < len; i++)
{
int k = 0;
for(int j = i; j < len; j++)
{
if(s[k]=='('&&s[j]==')' || s[k]=='['&&s[j]==']')
dp[k][j] = dp[k+1][j-1] + 2;
for(int l = k; l < j; l++)
dp[k][j] = max(dp[k][j], dp[k][l]+dp[l+1][j]);
k++;
}
}
printf("%d\n", dp[0][len-1]);
}
return 0;
}
hdu4283
大致意思就是导演想要知道怎么使男孩的失望值最低，因为题目说的是先入后出，所以要反过来枚举
#define CLR(x) memset(x, 0, sizeof(x))
const int N = 105;
int D[N], dp[N][N];
int sum[N];
int main()
{
int T;
scanf("%d", &T);
int k = 1;
while (T--)
{
CLR(D); CLR(dp); CLR(sum);
sum[0] = 0;
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &D[i]);
sum[i] = sum[i-1] + D[i]; // get所有区间的值
}
for (int i = n; i >= 1; i--)
for (int j = i; j <= n; j++)
{
dp[i][j] = INF;
for (int d = 1; d <= j-i+1; d++)
{
int k = i+d-1;
dp[i][j] = min (dp[i][j], dp[i+1][k]+dp[k+1][j]+(d-1)*D[i]+d*(sum[j]-sum[k]));
}
}
printf("Case #%d: %d\n", k++, dp[1][n]);
}
}
hdu2476
这题题目有毒！！！！
阿西吧，读了两个小时没读懂，可能是我菜吧，最后查了题解才搞懂题目意思
分析一下样例，他题目中所谓的刷一下是这样的
0：zzzzzfzzzzz
1：aaaaaaaaaaa [0，10]
2：abbbbbbbbba [1，9]
3：abcccccccba [2，8]
4：abcdddddba [3，7]
5：abcdeeedba [4，6]
6：abcdefedba [5]
上代码
const int N = 105;
int dp[N][N];
char a[105], b[105];
int ans[105];
int main()
{
while (scanf("%s%s", a, b) != EOF)
{
int len = strlen(a);
for (int i = 0; i < len; i++)
{
for (int j = i; j >= 0; j--)
{
dp[j][i] = dp[j+1][i] + 1;
for (int k = j+1; k <= i; k++)
if (b[j] == b[k])
dp[j][i] = min(dp[j][i], dp[j+1][k]+dp[k+1][i]);
}
ans[i] = dp[0][i];
}
for (int i = 0; i < len; i++)
{
if (a[i] == b[i]) ans[i] = ans[i-1];
else
{
for (int j = 0; j < i; j++)
ans[i] = min(ans[i], ans[j]+dp[j+1][i]);
}
}
printf("%d\n", ans[len-1]);
}
}
下面就是笔者之前提过，真正有可能在比赛中出现的区间DP，带几何计算的。
ZOJ3537
大致题意：给你一堆的点（二维坐标的），问又他们构成的多边形能不能切成三角形，如果可以求出它的最小代价，对，每切一刀都是有代价的（costi, j = |xi + xj| * |yi + yj| % p. ）
这是个凸包判断+三角剖分+区间DP的问题
GG上板子上板子
#define CLR(x) memset(x, 0, sizeof(x))
int dp[305][305], cost[305][305];
int n, P;
struct point
{
double x, y;
} p[305], tmp[305];
bool mult(point st, point ed, point p)
{
return (st.x-p.x)*(ed.y-p.y) >= (ed.x-p.x)*(st.y-p.y);
}
bool operator < (const point &a, const point &b)
{
return a.y<b.y || (a.y==r.y && a.x<b.x);
}
int Graham(point pnt[], int n, point res[])
{
sort(pnt, pnt + n);
if (n == 0) return 0; res[0] = pnt[0];
if (n == 1) return 1; res[1] = pnt[1];
if (n == 2) return 2; res[2] = pnt[2];
int top = 1;
for (int i = 2; i < n; i++)
{
while (top && mult(pnt[i], res[top], res[top-1])) top--;
res[++top] = pnt[i];
}
int len = top;
for (int i = n - 3; i >= 0; i--)
{
while (top!=len && mult(pnt[i], res[top], res[top-1])) top--;
res[++top] = pnt[i];
}
return top;
}
int cal(int i, int j)
{
return abs((int)tmp[i].x+(int)tmp[j].x) * abs((int)tmp[i].y+(int)tmp[j].y) % P;
}
int main()
{
while (scanf("%d%d", &n, &P) != EOF)
{
CLR(p); CLR(tmp); CLR(cost);
for (int i = 0; i < n; i++)
scanf("%lf%lf", &p[i].x, &p[i].y);
if (n <= 3) printf("0\n");
else if (Graham(p, n, tmp) < n) printf("I can't cut.\n");
else
{
for (int i = 0; i < n; i++)
for (int j = i+2; j < n; j++)
cost[i][j] = cost[j][i] = cal(i, j);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
dp[i][j] = INF;
dp[i][(i+1)%n] = 0; //dp[i][i+1]=0(i!=n-1) dp[n-1][0]=0
}
for (int i = n-3; i >= 0; i--)
for (int j = i+2; j < n; j++)
for (int k = i+1; k <= j; k++)
dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]+cost[i][k]+cost[k][j]);
printf("%d\n", dp[0][n-1]);
}
}
return 0;
}
这题的区间DP公式很简单。。。就是几何计算坑！！！
