Luogu

SPOJ

算法

考虑线性DP。

设$f[i][j][0]$表示$i$小时休息了$j$小时，并且第$i$小时不在休息的最大值，$f[i][j][1]$表示$i$小时休息了$j$小时，并且第$i$小时在休息的最大值。

显然有：

$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][1]+a[i],f[i-1][j-1][0])$

边界为$f[1][0][0]=f[1][1][1]=0$，答案为$max(f[n][b][0],f[n][b][1])$。

可惜，这样的做法会WA，原因是第一天的最后一个小时和第二天的第一个小时是连着的。

也就是说，上面的DP少了第一个小时获得了$a[1]$点体力的情况。

那么令边界为$f[1][1][1]=a[1]$，再DP一次即可。此时答案为$f[n][b][1]$。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int max_(int a,int b) { if (a>b) return a; else return b; }
inline int min_(int a,int b) { if (a<b) return a; else return b; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int n,b,ans=-1;
int a[4010];
int f[2][4010][2];

int main() {
    int T=read();
    while (T--) {
        memset(f,128,sizeof(f)); ans=-1;
        
        n=read(),b=read();
        for (re int i=1;i<=n;i++) a[i]=read();
        
        f[1][0][0]=f[1][1][1]=0;
        for (re int i=2;i<=n;i++) {
            int now=i&1,pre=now^1;
            for (re int j=0;j<=min_(i,b);j++) {
                f[now][j][0]=max_(f[pre][j][0],f[pre][j][1]);
                if (j) f[now][j][1]=max_(f[pre][j-1][1]+a[i],f[pre][j-1][0]);
            }
        }
        ans=max_(f[n&1][b][0],f[n&1][b][1]);
        
        memset(f,128,sizeof(f)); f[1][1][1]=a[1];
        for (re int i=2;i<=n;i++) {
            int now=i&1,pre=now^1;
            for (re int j=0;j<=min_(i,b);j++) {
                f[now][j][0]=max_(f[pre][j][0],f[pre][j][1]);
                if (j) f[now][j][1]=max_(f[pre][j-1][1]+a[i],f[pre][j-1][0]);
            }
        }
        ans=max_(ans,f[n&1][b][1]);
        printf("%d\n",ans);
    }
    return 0;
}