【区间DP】释放囚犯-白红宇

【区间DP】释放囚犯

阅读量：5252 次

发布时间：2019-06-14

本文共 1261 字，大约阅读时间需要 4 分钟。

貌似和石子合并差不多

~~可能是我见的题太少了，所以都差不多~~

算法分析

首先不难看出这是一道区间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
    
     #include
     
      #include
      
       #include
       
        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<