题解 SP283 【NAPTIME - Naptime】

YanLei · 2020-11-20 19:09:02 · 题解

Naptime | SP283

详情见CSDN博客：【训练题15：线性DP(如何时间复杂度一降再降)】Naptime | SP283

难度

• 有趣的题目！
• 主要是考察如何转移以及如何降低时间复杂度。

独立写出

题意

• 在某个星球上，一天由 N 小时构成。
• 在第 i 个小时睡觉能恢复 U_i 点体力。
• 在这座星球上住着一头牛，它每天要休息 B 个小时，它休息的这 B 个小时可以不连续，可以分成若干段，但是在每一段的第一个小时不能恢复体力，从第二个小时开始才可以恢复体力。
• 为了身体健康，这头牛希望遵循生物钟，每天采用相同的睡觉计划。
• 另外，因为时间是连续的，每天的第 N 个小时与下一天的第一个小时是相连的，这头牛只需要在 N 个小时内休息 B 个小时就够了。
• 请你给这头牛安排一个任务计划，使得它每天恢复的体力最多。

数据范围

Sample

五天，睡三个小时

则它睡 U_4、U_5、U_6这三个时间段，获得收益为 1*0+4+2

思路

1.【暴力枚举法（没学过DP）】

• 暴力枚举每个时间段选或者不选，是最最简单的思路。
• 时间复杂度 \color{cyan}O(2^NN)
• 继续努力想想嘛。

2.【区间DP / 三维 DP 写法】

• 设 dp[i][j][k]表示区间 i\sim j选择睡觉 k 个小时的获得最大体力值。
• 考虑转移还要枚举中间断点，时间复杂度：\color{cyan}O(N^4)
• 当状态维度过大，我们会试着降低一个维度看看效果。

3.【线性DP / 二维 DP 单状态，多转移法】

• 设 dp[i][j]表示区间 1\sim i选择睡觉 j 个小时的获得最大体力值。
• 转移方程我们可以轻松写出：
• dp[i+m][j+m]=\max\{dp[i][j]+get[i+1][j]\}
• 其中 get[a][b] 表示这一段区间的体力值的和，可以使用前缀和来优化到 O(1) 获得。
• 我们可以发现，状态数有 O(N^2) ， 每一个状态的转移种数又有 O(N)
• 所以时间复杂度为 \color{cyan}O(N^3) （不加前缀和优化的话还要乘以一个 N）
• 尽管状态数少了，但是转移的方式还是很多，需要考虑如何转移才可以 O(1) 转移。

4.【线性DP / 二维 DP 多状态，单转移法】

• 设 dp[i][j][0] 表示区间 1\sim i选择睡觉 j 个小时，并且当前不睡觉时获得最大体力值
• 设 dp[i][j][1] 表示区间 1\sim i选择睡觉 j 个小时，并且刚刚睡觉一个小时时获得最大体力值
• 设 dp[i][j][2] 表示区间 1\sim i选择睡觉 j 个小时，并且现在已经睡觉大于一个小时时获得最大体力值

这样，状态转移方程便可以很好地推出了。

• dp[i][j][0]=\max\{dp[i-1][j][0],dp[i-1][j][1],dp[i-1][j][2]\}
• dp[i][j][1]=dp[i-1][j-1][0]
• dp[i][j][2]=\max\{dp[i-1][j-1][1],dp[i-1][j-1][2]\}+U_i
• 式子一：当前不睡觉等于前一状态已经睡了 j 小时的最大值。
• 式子二：当前睡第一轮等于前一状态少睡一个小时，并且还没睡觉的值。
• 式子三：当前睡多轮等于前一状态少睡一小时，并且在睡觉的最大值。
• 时间复杂度直接变成 \color{cyan}O(N^2)，感觉已经成功了！

真的成功了吗？

• 因为一天的时间不一定要从早上开始的一天，也可以是从中午开始到第二天中午的一天。比如样例，答案就是跨过一天的。
• 如果我们枚举从哪一个时间开始作为一天的开始的话，时间复杂度又要再乘上一个 N ，似乎又成了一个瓶颈！

想法一：把一天扩展成两天

• 如果一天是 U=2\ 0\ 3\ 1\ 4，我们不试一下把两天拼接起来
• 使之变成 U=2\ 0\ 3\ 1\ 4\ 2\ 0\ 3\ 1\ 4
• 然后再去计算最后的答案呢？

结果：

• 这样会导致答案错误。比如他可能会同时在两天的上午睡觉，但这不符合题目要求。

想法二：越单纯越好

• 考虑到：因为第一个小时的睡觉是不回复体力值的。如果要我们贪心的话，肯定是第一个小时会选择尽可能小的值。
• 那我们为何不选出一个小时，这个小时是我们一定不会选择在这个小时获得休息值的呢？ 然后选择把这个小时放在这天的第一个小时，当做新的一天的第一个小时。这样我们选择的结果就不会跨过新的一天的结尾了。

这样子就成功了！

核心代码

时间复杂度 O(N^2)

/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
        __/ |
       |___/
*/
const int MAX = 4e3+50;
const int INF = 0x3f3f3f3f;

int aa[MAX];
int bb[MAX];
int dp[MAX][MAX][4];
int main()
{
    int T;scanf("%d",&T);
    while(T--){
        int N,B;
        scanf("%d%d",&N,&B);
        int mn = INF;
        int id = 0;
        for(int i = 1;i <= N;++i){
            scanf("%d",&bb[i]);
            if(bb[i] < mn){
                mn = bb[i];
                id = i;
            }
        }
        for(int i = 1;i <= N;++i){
            aa[i] = bb[(id + i - 1 - 1) % N + 1];
        }
        for(int i = 0;i <= N;++i)
        for(int j = 0;j <= B;++j)
        for(int k = 0;k <= 2;++k)
            dp[i][j][k] = -LINF;

        for(int i = 0;i <= N;++i){
            dp[i][0][0] = 0LL;
        }
        for(int i = 1;i <= N;++i){
            for(int j = 1;j <= min(i,B);++j){
                dp[i][j][0] = max(max(dp[i-1][j][0],dp[i-1][j][1]),dp[i-1][j][2]);
                dp[i][j][1] = dp[i-1][j-1][0];
                dp[i][j][2] = max(dp[i-1][j-1][1],dp[i-1][j-1][2]) + aa[i];
            }
        }
        int ans = 0;
        for(int i = B;i <= N;++i){
            for(int j = 0;j < 3;++j){
                ans = max(ans,dp[i][B][j]);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}