题解 SP283 【NAPTIME - Naptime】

· · 题解

首先假设一天的第N小时与后一天的第一个小时不相连， 这种情况下DP转移比较好想

考虑一天的**前i个小时**，**已经休息了j小时**，且**第i个小时是否在休息** 那么有状态转移方程 ``` dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]); dp[i][j][1]=max(dp[i-1][j-1][0],dp[i-1][j-1][1]+a[i]); ``` 初始化为$dp[1][0][0]=dp[1][1][1]=0$， 其余为$-inf

答案为max(dp[n][b][0],dp[n][b][1])

现在再考虑一天的第N小时与后一天的第一个小时相连

我们发现上述转移中， 唯一没考虑到的情况只有第1个小时休息能获得体力

于是我们可以初始化dp[1][1][1]=U_1， 转移方程与上述相同

那么答案为dp[n][b][1](即强制最后一小时休息令第一小时能获得体力)， 和前一次dp的答案比较即可得到最终结果

到此为止在这里已经可以AC， 但是！！！如果我们拿到POJ上提交， 你会发现自己疯狂MLE(POJ丧心病狂的Memory limit只有64M)

于是我们考虑用滚动数组优化空间

dp[i&1][j][0]=max(dp[(i-1)&1][j][0],dp[(i-1)&1][j][1]);
dp[i&1][j][1]=max(dp[(i-1)&1][j-1][0],dp[(i-1)&1][j-1][1]+a[i]);

因为dp[i][][]只与dp[i-1][][]有关， 所以只要交替使用数组第0维和第1维， 只保存上一次更新的dp数组， 即可大幅优化空间

//niiick
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
#include<map>
using namespace std;
typedef long long lt;

int read()
{
    int x=0,f=1;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return x*f;
}

const int maxn=4010;
int t,n,m,ans;
int a[maxn];
int dp1[2][maxn][2],dp2[2][maxn][2];

int main()
{
    t=read();
    while(t--)
    {
        n=read();m=read();ans=0;
        for(int i=1;i<=n;++i)a[i]=read();

        memset(dp1,128,sizeof(dp1));
        dp1[1][0][0]=dp1[1][1][1]=0;

        memset(dp2,128,sizeof(dp2));
        dp2[1][1][1]=a[1];

        for(int i=2;i<=n;++i)
        for(int j=0;j<=min(i,m);++j)
        {
            dp1[i&1][j][0]=max(dp1[(i-1)&1][j][0],dp1[(i-1)&1][j][1]);
            if(j>=1)dp1[i&1][j][1]=max(dp1[(i-1)&1][j-1][0],dp1[(i-1)&1][j-1][1]+a[i]);

            dp2[i&1][j][0]=max(dp2[(i-1)&1][j][0],dp2[(i-1)&1][j][1]);
            if(j>=1)dp2[i&1][j][1]=max(dp2[(i-1)&1][j-1][0],dp2[(i-1)&1][j-1][1]+a[i]);
        }
        ans=max(dp2[n&1][m][1],max(dp1[n&1][m][1],dp1[n&1][m][0]));
        printf("%d\n",ans);
    }
    return 0;
}