传送门
区间DP简介：
在写这题前，需要先弄清楚区间DP是如何操作的：
区间DP的做法还是相对固定的，没有其他类型DP的复杂多变。主要思想就是先在小区间进行DP得到最优解，然后再利用小区间的最优解合并求大区间的最优解。实现起来也十分简单，即枚举区间长度，再枚举左端点，之后枚举区间的断点进行转移。（不同的题目，有不同的转移方式）。
下面给出区间DP最简单形式的伪代码(具体要根据题目修改)
//mst(dp,0) 初始化DP数组 for(int i=1;i<=n;i++) { dp[i][i]=初始值 } for(int len=2;len<=n;len++) //区间长度 for(int i=1;i<=n;i++) //枚举起点 { int j=i+len-1; //区间终点 if(j>n) break; //越界结束 for(int k=i;k<j;k++) //枚举分割点，构造状态转移方程 { dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+w[i][j]); } }
题解：
区间dp的套路：设 f [ i ] [ j ] 为区间释放 i ~ j 号囚犯所需最少的肉（注意， i , j 不是牢房编号，是释放的囚犯编号，也就是下面的 a [ i ] 数组）
枚举区间的分界点 k ，转移方程为：
f [ i ] [ j ] =min { f [ i ] [ j ] , f [ i ] [ k-1 ] + f [ k+1 ] [ j ] + a [ j+1 ] - a [ i-1 ] -1 -1 }
把后面这一块拿出来拆开看看， f [ i ] [ k-1 ] + f [ k+1 ] [ j ] + a [ j+1 ] - a [ i-1 ] -1 -1
f [ i ] [ k-1 ] + f [ k+1 ] [ j ]，这个不必解释
a [ j+1 ] - a [ i-1 ] -1就是第 j+1 个要放出的囚犯到第 i-1 个要放出的囚犯之间的人数，也就是要发的肉的数量；
最后一个 -1 是什么呢，就是第k个放出去的囚犯，不用给他吃肉了
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<cstdlib> #include<iostream> #include<stack> #include<queue> #include<deque> #include<vector> #include<map> #include<set> using namespace std; #define INF 0x3f3f3f3f #define maxn 2501 int n,m; int a[maxn]; int f[maxn][maxn]; inline int read() { char kr=0; char ls; for(;ls>'9'||ls<'0';kr=ls,ls=getchar()); int xs=0; for(;ls>='0'&&ls<='9';ls=getchar()) { xs=xs*10+ls-48; } if(kr=='-') xs=0-xs; return xs; } int main() { n=read();m=read(); for(int i=1;i<=m;i++) { a[i]=read(); } sort(a+1,a+m+1);//排序，有序的才能转移状态 a[0]=0;a[m+1]=n+1;//假设0和n+1号牢房有人，方便后面的状态转移（我就因为没有初始化输出负数） for(int l=1;l<=m;l++)//枚举区间长度 for(int i=1;i+l-1<=m;i++)//区间左端点位置 { int j=i+l-1;//区间右端点位置 f[i][j]=INF; for(int k=i;k<=j;k++)//枚举分界点 f[i][j]=min(f[i][j],f[i][k-1]+f[k+1][j]+a[j+1]-a[i-1]-1-1); //状态转移 } printf("%d ",f[1][m]);//输出 return 0; }