传送门
解题思路
感觉还是蛮有难度的。
设dp[i][j]表示释放编号在区间i..j的犯人所需要的肉的数量。
一开始枚举最后一个释放的人k进行转移，结果发现wa了，为什么？
深入分析一下，发现不满足无后效性，即未来的决策会影响现在的答案。
因为k左右两边的转移是相互影响的。
而当我们枚举的k的意义变成第一个释放的人，就会正确。
因为k使得左右区间间隔开，不会互相影响到。
剩下的就是普通的区间dp了。
AC代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=105;
int n,m,a[maxn],dp[maxn][maxn];
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>a[i];
sort(a+1,a+m+1);
a[m+1]=n+1;
for(int i=1;i<=m;i++) dp[i][i]=a[i+1]-a[i-1]-2;
for(int len=2;len<=m;len++){
for(int i=1;i<=m;i++){
int j=i+len-1;
if(j>m) break;
dp[i][j]=min(dp[i+1][j],dp[i][j-1])+a[j+1]-a[i-1]-2;
for(int k=i;k<=j;k++){
dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]+a[j+1]-a[i-1]-2);
}
}
}
cout<<dp[1][m];
return 0;
}