P1622释放囚犯

逃离我推掉我的手 2021-10-29 09:12 179阅读 0赞

这是一道绿题，是一道让人想用贪心但却是区间DP的题目，难倒了我这个蒟蒻。

这个题其实仔细观察是类似于石子合并的！合并石子的代价便是肉的数量，求最小代价。所以我们设dp\[i\]\[j\]为释放第i个到第j个所花费的代价，先用sum\[i\]求出每一个节点(犯人1与起点间的人数，犯人i+1与犯人i间的人数，终点与犯人q间的人数，也就是前缀和（还要-1）然后进行区间DP。首先枚举区间的长度，嵌套枚举区间的起点，那么区间的终点便可以得到，然后令dp\[i\]\[j\]=0xfffffff后枚举分割点，看先释放哪个囚犯更好。于是得出状态转移方程dp\[i\]\[j\]=max(dp\[i\]\[j\],dp\[i\]\[k\]+dp\[k+1\]\[j\]+sum\[j\]-sum\[i-1\]+j-i-1;

**1.看到一个题后，想是否万变不离模板题**

**2.区间DP处理好前缀和或者后缀和，勿漏情况**

**3.注意第j个与第i个间有j-1-1人**

**4.状态转移方程写全面，可以代入验证正确性，也别光按照原理判断**

代码

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #define N 1005
    using namespace std;
    int dp[N][N];
    int p,q;
    int a[N]={
        0},sum[N]={
        0};
    int main(){
        scanf("%d%d",&p,&q);
        for(int i=1;i<=q;i++){
            scanf("%d",&a[i]);
        }
        a[0]=0;
        a[++q]=p+1;
        sort(a,a+1+q);
        for(int i=1;i<=q;i++){
            sum[i]=a[i]-a[i-1]-1+sum[i-1];//前缀和,代表它前面需要有几个不放给多少个肉 
            //cout<<sum[i]<<endl;
        } 
        for(int l=2;l<=q;l++){
        //枚举长度 
            for(int i=1;i+l-1<=q;i++){
        //枚举起点 
                int j=i+l-1;
                dp[i][j]=0xffffff;
                for(int k=i;k<j;k++){
        //枚举分割点 
                    if(dp[i][j]>dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]+j-i-1){
                        dp[i][j]=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]+j-i-1;
                    //j-i-1代表需要释放但还没释放的人的代价 
                    }
                }
            }
        }
        printf("%d",dp[1][q]);
        return 0;
    }

转载于:https://www.cnblogs.com/china-mjr/p/11261427.html