题解【洛谷P6064】[USACO05JAN]Naptime G

题面

一道环形 DP 题。

首先设 (dp_{i,j,0/1}) 表示前 (i) 个小时中睡了 (j) 个小时，且第 (i) 个小时 不睡觉 / 睡觉 能得到的最大效用值。

状态的转移其实很好想：

• 如果第 (i) 个小时不睡觉，那么肯定是前 (i-1) 个小时中睡了 (j) 个小时，所以 (dp_{i,j,0}=max{dp_{i-1,j,0},dp_{i-1,j,1}})；
• 如果第 (i) 个小时睡觉，那么前 (i-1) 个小时中睡了 (j-1) 个小时，还需要考虑一下第 (i) 个小时是不是当睡觉时间段的第一个小时，所以 (dp_{i,j,1} = max{dp_{i-1,j-1,0},dp_{i-1,j-1,1}+a_i})（(a_i) 为第 (i) 个小时的效用值）。

值得注意的是，我们需要做两次 DP：

• 第一次 DP 表示第 (n) 个小时睡觉，初始值为 (dp_{1,0,0}=0)，(dp_{1,1,1}=a_1)；
• 第二次 DP 表示第 (n) 个小时不睡觉，初始值为 (dp_{1,0,0}=0)，(dp_{1,1,1}=0)。

空间可能比较卡，需要开滚动数组优化空间。

#include <bits/stdc++.h>

using namespace std;

const int N = 3843;

int n, m;
int dp[2][N][2];
int a[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i+=1) cin >> a[i];
    memset(dp, 0xcf, sizeof dp);
    // 第 n 小时 睡觉
    dp[1][0][0] = 0, dp[1][1][1] = a[1];
    for (int i = 2; i <= n; i+=1)
        for (int j = 0; j <= m; j+=1)
        {
            dp[i & 1][j][0] = max(dp[i - 1 & 1][j][0], dp[i - 1 & 1][j][1]);
            if (j > 0) dp[i & 1][j][1] = max(dp[i - 1 & 1][j - 1][0], dp[i - 1 & 1][j - 1][1] + a[i]);
        }
    int ans = dp[n & 1][m][1];    
    memset(dp, 0xcf, sizeof dp);
    // 第 n 小时 不睡觉
    dp[1][0][0] = 0, dp[1][1][1] = 0;
    for (int i = 2; i <= n; i+=1)
        for (int j = 0; j <= m; j+=1)
        {
            dp[i & 1][j][0] = max(dp[i - 1 & 1][j][0], dp[i - 1 & 1][j][1]);
            if (j > 0) dp[i & 1][j][1] = max(dp[i - 1 & 1][j - 1][0], dp[i - 1 & 1][j - 1][1] + a[i]);
        }
    cout << max(ans, dp[n & 1][m][0]) << endl;
    return 0;
}