Loading... [题目链接](https://www.luogu.org/problemnew/show/P1622 "题目链接") <!--more--> #### 区间dp $f\[i\]\[j\]$表示释放$i$\\~$j$的罪犯所需要的最少的肉,转移枚举分界点$k$。 转移方程:$f\[i\]\[j\]=min(f\[i\]\[j\],f\[i\]\[k-1\]+f\[k+1\]\[j\]+a\[j+1\]-a\[i-1\]-1)$ $a\[j+1\]-a\[i-1\]-1$就是第$i-1$到$j+1$个罪犯之间的人数,及所需肉的数量。 - 注意,上述方程需要满足单调性,所以先排序。 #### 代码如下: ```cpp #include<bits/stdc++.h> using namespace std; int a[1009],f[109][109]; int n,m; int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ cin>>a[i]; f[i][i]=n-1; } a[m+1]=n+1; sort(a+1,a+m+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]=0x3f3f3f3f; for(int k=i;k<=j;k++){ if(f[i][j]>f[i][k-1]+f[k+1][j]+a[j+1]-a[i-1]-2) f[i][j]=f[i][k-1]+f[k+1][j]+a[j+1]-a[i-1]-2; } } } cout<<f[1][m]; return 0; } ``` Last modification:March 14, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用,请随意赞赏