题目内容

P6064

大意:贝茜是一只非常缺觉的奶牛.她的一天被平均分割成 N 段(3 \leq N \leq 3830),但是她要用其中的 B 段时间(2 \leq B \lt N)睡觉。每段时间都有一个效用值 U_i,只有当她睡觉的时候,才会发挥效用。

有了闹钟的帮助,贝茜可以选择任意的时间入睡,当然,她只能在时间划分的边界处入睡、醒来。

贝茜想使所有睡觉效用的总和最大。不幸的是,每一段睡眠的第一个时间阶段都是“入睡”阶段,而旦不记入效用值。

时间阶段是不断循环的圆(一天一天是循环的嘛)。

解题思路

我的第一个想法是将两天并成一起考虑,就很方便的能考虑到连起来的两天的问题。

然而这个做法是假的,因为没有考虑到两天中的同一个小时都被统计进去的情况,所以 WA 的很惨。

后面通过学习,发现可以另辟蹊径,直接暴力分开考虑到底第一段时间是不是接着昨天的最后一段时间来进行考虑。

此题的状态定义不难,可定义 f_{i,j,k} 表示到第 i 段时间结束为止,一共睡了 j 个小时,k=0 表示第 i 段时间为清醒状态,为 1 则表示为睡眠状态。则转移显然为:

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}+u_i)

实际上就是考虑睡不睡觉来进行转移的问题

#include <cstdio>
#include <cctype>
#include <cstring>

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

inline int max(int a,int b)
{
    return a>b?a:b;
}

inline int min(int a,int b)
{
    return a<b?a:b;
}

const int maxn=3850;

int n,b,u[maxn],f[maxn][maxn][2];

void init()
{
    n=read(),b=read();
    for(int i=1;i<=n;i++)
        u[i]=read();
    return;
}

int main()
{
    int ans=0;
    init();
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=min(i,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],j==1?0:f[i-1][j-1][1]+u[i]);
            //转移时需要考虑如果j==1的话是无法+u[i]的
        }
    }
    ans=max(ans,max(f[n][b][0],f[n][b][1]));//第一遍计算答案,考虑睡眠不跨天
    memset(f,0,sizeof f);
    f[1][1][1]=u[1];//初始化,考虑睡眠跨天,即强制睡第一个小时
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=min(i,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],j==1?0:f[i-1][j-1][1]+u[i]);
        }
    }
    ans=max(ans,f[n][b][1]);//第二遍统计答案,因为睡眠跨天所以只能统计 f[n][b][1]
    printf("%d\n",ans);
    return 0;
}
最后修改日期:2020年8月30日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。