Luogu SP283 Naptime

September 14, 2019

1225 views

741 words

蓝书环形dp第一题

- 在一天当中，如果时间从1点开始，那么如果在线性时间上（时间只能从1到N），那么显然根据题意，1点时肯定不能处于熟睡状态，所以：$f[i][j][0/1]$表示前i个小时里睡了j小时，并且第i小时在（1）不在（0）睡觉，显然$f[1][0][0] = 0,f[1][1][1]=0$其余初始化为$-\infty$那么：
- $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]+w_i)$
- 目标状态就是$max(f[n][k][1], f[n][k][0])$

那么如果这只是一个序列上的问题，这样就写完了，但是它第N个小时和第1个小时是连起来的，所以我们可以强制1点在或不在睡觉，取最大值即可。
- $f[1][1][1]=w_1$其余初始化为$-\infty$，转移方程相同。
- 目标状态是$f[n][k][1]$因为想要1时时有恢复，必须至少保证n点时在睡觉。

```cpp
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;

int T, n, k;
int a[3849], f[3849][3849][2];

int main(){
    scanf("%d", &T);
    while(T--){
        memset(f, -0x3f, sizeof(f));
        scanf("%d%d", &n, &k);
        for(int i = 1; i <= n; i++){
            scanf("%d", &a[i]);
        }
        f[1][0][0] = 0;
        f[1][1][1] = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= min(i, k); j++){
                f[i][j][0] = max(f[i][j][0], max(f[i - 1][j][0], f[i - 1][j][1]));
                if(j >= 1) f[i][j][1] = max(f[i][j][1], max(f[i - 1][j - 1][0], f[i - 1][j - 1][1] + a[i]));
            }
        }
        int ans = max(f[n][k][1], f[n][k][0]);
        memset(f, -0x3f, sizeof(f));
        f[1][1][1] = a[1];
        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= min(i, k); j++){
                f[i][j][0] = max(f[i][j][0], max(f[i - 1][j][0], f[i - 1][j][1]));
                if(j >= 1) f[i][j][1] = max(f[i][j][1], max(f[i - 1][j - 1][0], f[i - 1][j - 1][1] + a[i]));
            }
        }
        ans = max(f[n][k][1], ans);
        printf("%d\n", ans);
    }
    return 0;
}
```

Last modification：March 14, 2020