（线式区间dp+环式结构+平行四边形优化）~~
所谓区间dp，顾名思义就是在一段区间上的动态规划，从小区间求得解开始向外部延伸的算法；
1.普遍情况下的核心代码：
for(int s=2;s<=n;s++)//枚举终点
{
for(int w=s-1;w>0;w--)//枚举起点
{
for(int k=w;k<=s;k++)//枚举断点
{
dp[w][s]=min(dp[w][s],dp[w][k]+dp[k+1][s]+改变的值);//或者max~看题意。
}
}
}2.经典的线式环境下的区间dp
（1）.sdnu 1045 http://www.acmicpc.sdnu.edu.cn/problem/show/1045（附帐号 heheda11 密码xiaoshibo0536）
1045.石子合并1
Description
有n堆石子排成一行，每次选择相邻的两堆石子，将其合并为一堆，记录该次合并的得分为两堆石子个数之和。已知每堆石子的石子个数，求当所有石子合并为一堆时，最小的总得分。
Input
第一行一个整数n(1 <= n <= 200)，表示石子堆数； 第二行n个整数a(1 <= a <= 100)，表示每堆石子的个数。
Output
一个整数，表示最小总得分。
Sample Input
5 7 6 5 7 100
Sample Output
175
Source
Unknown
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int dp[205][205];//dp【s】【w】表示从s到w的最少的费用
int sum[205];//表示前n项和
int n;
void cla()
{
for(int s=2;s<=n;s++)
{
for(int w=s-1;w>0;w--)
{
for(int k=w;k<=s;k++)
{
dp[w][s]=min(dp[w][s],dp[w][k]+dp[k+1][s]+sum[s]-sum[w-1]);//假设要把这两部分合成那么额外的费用就是从w到s的堆中数量和，即sum[s]-sum[w-1]
}
}
}
}
int main()
{
cin>>n;
memset(sum,0,sizeof(sum));//初始化
memset(dp,0x3f,sizeof(dp));
for(int s=1;s<=n;s++)
{
int a;
scanf("%d",&a);
sum[s]=sum[s-1]+a;
dp[s][s]=0;
}
cla();
printf("%d\n",dp[1][n]);
return 0;
}
1048.石子合并2
Description
有n堆石子排成一圈，每次选择相邻的两堆石子，将其合并为一堆，记录该次合并的得分为两堆石子个数之和。已知每堆石子的石子个数，求当所有石子合并为一堆时，最小的总得分。
Input
第一行一个整数n(1 <= n <= 200)，表示石子堆数； 第二行n个整数a(1 <= a <= 100)，表示每堆石子的个数，这些石子首尾相接排成一圈。
Output
一个整数，表示最小总得分。
Sample Input
5 7 6 5 7 100
Sample Output
175
Source
Unknown
之前的时候我们是线性的方法~那么环式的我们怎么解决呢~
很简单，再克隆一个串穿在第n个数据后面，来表面上形成2个串，这样计算的时候就会全部考虑到了。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int dp[2005][2005];//最小的费用
int sum[2005];//前n项和
int m[2005];//数据
int best[2005][2005];
int n;
void cla()
{
for (int s = 2; s <= 2 * n; s++)//枚举后端
{
for (int w = s - 1; w>0 && s - w<n; w--)//枚举前端
{
for (int k = best[w][s - 1]; k <= best[w + 1][s]; k++)//枚举断点
{
if (dp[w][s]>dp[w][k] + dp[k + 1][s] + sum[s] - sum[w - 1])
{
dp[w][s] = dp[w][k] + dp[k + 1][s] + sum[s] - sum[w - 1];
best[w][s] = k;
}
}
}
}
}
int main()
{
cin >> n;
memset(sum, 0, sizeof(sum));
memset(dp, 0x3f3f3f, sizeof(dp));
for (int s = 1; s <= n; s++)
{
scanf("%d", &m[s]);
m[s + n] = m[s];
}
for (int s = 1; s <= 2 * n; s++)
{
sum[s] = sum[s - 1] + m[s];
dp[s][s] = 0;
best[s][s] = s;
}
cla();
int ans = 0x3f3f3f3f;
for (int s = 1; s <= n; s++)//因为是环形所以要去全部查询一编
{
ans = min(ans, dp[s][s + n - 1]);
}
cout << ans << endl;
return 0;
}然后我们在说一下之中填的best函数~~这个里面记录的是best[w][s]是指从w到s的分割的最优的那个断点的位置是哪里~~具体的细节你们可以看一下平行四边形优化法则（http://www.cnblogs.com/jiu0821/p/4493497.html）~~这样的话可以优化成n^2的状态~。
投递完美世界等公司10个岗位 >