Luogu SP283 Naptime

蓝书环形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点时在睡觉。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×