题解 SP283 【NAPTIME - Naptime】

Azuree · 2019-11-04 15:55:59 · 题解

分类讨论

例题：SP283 NAPTIME - Naptime

对于这类问题，我们可以分类讨论首尾的状态，然后分别进行一次DP求得所有可能中的最优解。

状态设计

然后我们强制奶牛从一天的最后一小时睡到第二天的第一个小时并进行一次dp。

初始化：

因为强制从一天的最后一小时睡到第二天的第一个小时，所以把f[1][1][1]初始化为a[1]，活动第一个小时睡觉时得到的体力，而且不从f[1][0][0]转移，所以把它赋成负无限，再转移时，取max会把该状态滤掉（也许会把不合法状态赋成-INF）。

更新答案：ans=max(ans,f[n][b][1])（因为强制从一天的最后一小时睡到第二天的第一个小时，所以此时最后一小时不睡觉的状态是不合法的，不用它去更新答案。）

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define re register

using namespace std;

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

int T,n,b,ans,a[100005],f[4005][4005][2];

int main()
{
    T = read();
    while(T--)
    {
        memset(f,0,sizeof(f));
        n = read(); b = read();
        for(re int i = 1; i <= n; i++) a[i] = read();
        for(re int i = 1; i <= n; i++)
            for(re int j = 1; j <= b; j++)
            {
                f[i][j][0] = max(f[i - 1][j][0],f[i - 1][j][1]);
                f[i][j][1] = max(f[i - 1][j - 1][0],(f[i - 1][j - 1][1] + a[i]) * (j > 1));
            }
        ans = max(f[n][b][0],f[n][b][1]);
        memset(f,0,sizeof(f));
        f[1][0][0] = -INF; f[1][1][1] = a[1];
        for(re int i = 2; i <= n; i++)
            for(re int j = 1; j <= b; j++)
            {
                f[i][j][0] = max(f[i - 1][j][0],f[i - 1][j][1]);
                f[i][j][1] = max(f[i - 1][j - 1][0],(f[i - 1][j - 1][1] + a[i]) * (j > 1));
            }
        ans = max(ans,f[n][b][1]);
        printf("%d\n",ans);
    }
    return 0;
}