貌似和石子合并差不多
可能是我见的题太少了，所以都差不多
OK
算法分析
首先不难看出这是一道区间DP，那么，按照本蒟蒻的意思
区间DP==三个循环for(int len=2;len<=n;len++) for(int l=1;l+len-1<=n;l++）
{
int r=l+len-1;
for(int k=l;k<=r;k++)
状态转移方程；
}
接下来就是推方程的事情了
设f[i][j]为释放掉i~j号囚犯的最小花费，那么,容易得出
f[l][r]=min(f[l][r],f[l][k-1]+f[k+1][r]+一个数)
方程前半部分很好想，某个要释放的囚犯的前面的人与后面的人要用的最小花费的和；关键是那“一个数”怎么表达出来；
简单分析一下发现，这个数就是 a[r+1]-a[l-1]-2,就是这个区间的总人数除去自己嘛
带入一组样例，发现OK，那么......
#include<iostream>
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
inline int read()
{
char chr=getchar();
int f=1,ans=0;
while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();}
while(isdigit(chr)) {ans=ans*10;ans+=chr-'0';chr=getchar();}
return ans*f;
}
int n,m,a[1005],sum[1005];
int dp[1005][1005];
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;
for(int len=1;len<=m;len++)
for(int l=1;l+len-1<=m;l++)
{
int r=l+len-1;
dp[l][r]=0x3f3f3f3f;//赋成最大值，后面方便取min
for(int j=l;j<=r;j++)
dp[l][r]=min(dp[l][r],dp[l][j-1]+dp[j+1][r]+a[r+1]-a[l-1]-2);
}
cout<<dp[1][m];
return 0;
}