题解 P6064 【[USACO05JAN]Naptime G】

· · 题解

双倍经验

先来考虑一个“简化版”：假设第N个小时与次日第一个小时不是相连的，那么这就是一个明显的DP题：

用dp_{i,j,0/1}来表示在第i个小时，已经休息了j个小时，0表示这个小时没在休息，1表示这个小时正在休息。

状态转移方程就是：

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]+u[i]);

初值：dp_{1,1,1}=0，dp_{1,0,0}=0，其余为-INF。

答案：\max(dp_{n,b,0},dp_{n,b,1})。

但问题是第N个小时与次日第一个小时是相连的，上面的方法不能直接用。既然这样，那就再来一次强制连接：

强制让第N个小时睡觉，让次日第一个小时熟睡。

状态转移方程如上。

初值：dp_{1,1,1}=u_{1}，dp_{1,0,0}=0，其余为-INF。

答案：dp_{n,b,1}

具体来说，我们可以先将第N个小时与次日第一个小时断开，然后用上面的“简化版”的方法来得到一个答案。再强制让第N个小时睡觉，让次日第一个小时熟睡，用上面讨论的强制连接的方法得到第二个答案，两者取最大值即可。

AC\ Code: 
#include<bits/stdc++.h>
using namespace std;
int dp[3831][3831][2],n,b,u[3831],ans;
int main() {
    scanf("%d%d",&n,&b);
    for(int i=1;i<=n;i++)scanf("%d",u+i);
    memset(dp,-0x3f,sizeof(dp));
    dp[1][1][1]=dp[1][0][0]=0;
    for(int i=2;i<=n;i++){
        dp[i][0][0]=dp[i-1][0][0];
        for(int j=1;j<=b;j++){
            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]+u[i]);
        }
    }
    ans=max(dp[n][b][0],dp[n][b][1]);
    memset(dp,-0x3f,sizeof(dp));
    dp[1][1][1]=u[1];
    dp[1][0][0]=0;
    for(int i=2;i<=n;i++){
        dp[i][0][0]=dp[i-1][0][0];
        for(int j=1;j<=b;j++){
            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]+u[i]);
        }
    }
    ans=max(ans,dp[n][b][1]);
    printf("%d\n",ans);
    return 0;
}

这是一个比较常见的解决环形DP的策略，一定要记住