题目链接

区间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$个罪犯之间的人数,及所需肉的数量。 - 注意,上述方程需要满足单调性,所以先排序。

代码如下:

    #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 14th, 2020 at 08:54 pm