POJ 2228 Naptime【环形DP】

ゝ一世哀愁。 2024-04-19 10:55 59阅读 0赞

在某个星球上，一天由 N 个小时构成，我们称0点到1点为第1个小时、1点到2点为第2个小时，以此类推。

在第 i 个小时睡觉能够恢复UiUi点体力。

在这个星球上住着一头牛，它每天要休息B个小时。

它休息的这B个小时不一定连续，可以分成若干段，但是在每段的第一个小时，它需要从清醒逐渐入睡，不能恢复体力，从下一个小时开始才能睡着。

为了身体健康，这头牛希望遵循生物钟，每天采用相同的睡觉计划。

另外，因为时间是连续的，即每一天的第N个小时和下一天的第1个小时是相连的（N点等于0点），这头牛只需要在每N个小时内休息够B个小时就可以了。

请你帮忙给这头牛安排一个睡觉计划，使它每天恢复的体力最多。

输入格式

第1行输入两个空格隔开的整数N和B。

第2..N+1行，第 i+1 行包含一个整数UiUi。

输出格式

输出一个整数，表示恢复的体力值。

数据范围

3≤N≤3830  
2≤B<N  
0≤Ui≤200000

思路：可以发现该问题形成了一个时间环，我们先考虑不成环的情况。定义状态dp\[i\]\[j\]\[0\]表示前i个小时休息了j个小时并且第i个小时没有睡的最大值，dp\[i\]\[j\]\[1\]表示前i个小时中休息了j个小时并且第i小时休息了的最大值，那么可以得到转移方程

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

边界dp\[1\]\[0\]\[0\] = dp\[1\]\[1\]\[1\] = 1, 目标状态为 max(dp\[n\]\[m\]\[0\], dp\[n\]\[m\]\[1\]).

再考虑是环形的情况，可以发现只有1没有考虑到，因为线性的时候起点是1，而环形的时候起点不一定是1

所以我们再考虑起点不是1的情况，另边界dp\[1\]\[1\]\[1\] = a\[1\], 目标状态就是dp\[n\]\[m\]\[1\]

题目限制了内存，所以用滚动数组优化一维。

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    #define ls rt << 1
    #define rs rt << 1|1
    #define mid ((l + r) >> 1)
    #define lson l, mid, ls
    #define rson mid + 1, r, rs
    const int maxn = 4e3 + 10;
    const int mod = 1e9 + 7;
    int a[maxn];
    int dp[2][maxn][2]; //前i个小时中休息了j个小时的最大值，0表示i小时没睡，1表示i小时睡了
    
    int main()
    {
        int n, m;
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        memset(dp, -0x3f, sizeof(dp));
        dp[1][0][0] = dp[1][1][1] = 0;
        for(int i = 2; i <= n; ++i)
        {
            for(int j = 0; j <= m; ++j)
            {
                dp[i & 1][j][0] = max(dp[(i - 1) & 1][j][0], dp[(i - 1) & 1][j][1]);
                if(j)
                    dp[i & 1][j][1] = max(dp[(i - 1) & 1][j - 1][0], dp[(i - 1) & 1][j - 1][1] + a[i]);
            }
        }
        int ans = max(dp[n & 1][m][1], dp[n & 1][m][0]);
        memset(dp, -0x3f, sizeof(dp));
        dp[1][1][1] = a[1];
        for(int i = 2; i <= n; ++i)
        {
            for(int j = 0; j <= m; ++j)
            {
                dp[i & 1][j][0] = max(dp[(i - 1) & 1][j][0], dp[(i - 1) & 1][j][1]);
                if(j)
                    dp[i & 1][j][1] = max(dp[(i - 1) & 1][j - 1][0], dp[(i - 1) & 1][j - 1][1] + a[i]);
            }
        }
        ans = max(ans, dp[n & 1][m][1]);
        printf("%d\n", ans);
        return 0;
    }