解题方向:
环上的 d p dp dp解题方法一般分为两种:
1.找不同集合去覆盖全部的集合,跑两次 d p dp dp。
2.破环成链。
休息时间
题意:
星球一天有 N N N个小时,一头牛每天要睡 B B B小时,在第 i i i个小时睡觉可以恢复 a [ i ] a[i] a[i]的体力。睡觉的时间可以分成若干段,但是每段的第一个小时是不恢复体力的。每一天的第 N N N个小时和下一天的第 1 1 1个小时是连续的,其只需在每 N N N个小时休息 B B B小时就够了,求可恢复的最多的体力。
思路:
显然,该题破环成链也可以做,但是时间复杂度太大。我们考虑一个简化的问题:第 N N N个小时和下一天的第 1 1 1个小时不相连。那么我们直接 f [ i , j , 0 / 1 ] f[i,j,0/1] f[i,j,0/1]表示前 i i i个小时休息了 j j j小时,且当前在不在休息。简单 d p dp dp即可。
我们可以把集合划分为两部分:
1.第 N N N个小时睡觉
2.第 N N N个小时睡觉
显然,我们的答案一定可以在其中之一取到。
我们仿照上述 d p dp dp跑两边即可,仅初始状态不一样。
code:
const int N = 4000 + 10, M = N * 2, mod = 998244353;
int n, m, a[N];
int f[2][N][2];
signed main() {
#ifdef JANGYI
freopen("input.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
read(n), read(m);
rep(i, 1, n) read(a[i]);
//第N个小时不睡觉
memset(f, -0x3f, sizeof f);
int now = 1;
f[0][0][0] = f[0][1][1] = 0;
for(int i = 2; i <= n; i++) {
for(int j = 0; j <= min(i, m); j++) {
f[now][j][0] = max(f[now ^ 1][j][0], f[now ^ 1][j][1]);
if(j) f[now][j][1] = max(f[now ^ 1][j - 1][0], f[now ^ 1][j - 1][1] + a[i]);
}
now ^= 1;
}
int ans = max(f[now ^ 1][m][0], f[now ^ 1][m][1]);
//第N个小时睡觉
memset(f, -0x3f, sizeof f);
now = 1;
f[0][1][1] = a[1];
for(int i = 2; i <= n; i++) {
for(int j = 0; j <= min(i, m); j++) {
f[now][j][0] = max(f[now ^ 1][j][0], f[now ^ 1][j][1]);
if(j) f[now][j][1] = max(f[now ^ 1][j - 1][0], f[now ^ 1][j - 1][1] + a[i]);
}
now ^= 1;
}
ans = max(ans, f[now ^ 1][m][1]);
cout << ans << '\n';
return 0;
}
ABC 251E:Takahashi and Animals
题意:
有 n n n个动物,每次可以花费 a [ i ] a[i] a[i]的代价给动物 i , i + 1 i,i+1 i,i+1喂一次食,花费 a [ n ] a[n] a[n]给 n , 1 n,1 n,1喂食。求最小代价给每个动物至少喂一次。
思路:
很明显,我们可以对集合进行如下划分:
1.动物 n , 1 n,1 n,1一起喂食
2.动物 n , 1 n,1 n,1不一起喂食
我们定义 f [ i , 0 / 1 ] f[i,0/1] f[i,0/1]表示前 i i i个动物中,当前动物是否和上一个动物一起喂食。
跑两边 d p dp dp即可。
code:
int n, a[N];
LL f[N][2]; // f[i][1/0]:前i个动物中,当前 是/否 是和上一个动物一起喂的
signed main() {
#ifdef JANGYI
freopen("input.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
read(n);
rep(i, 1, n) read(a[i]);
//第1个动物不和第n个一起喂食
memset(f, 0x3f, sizeof f);
f[1][0] = 0;
for(int i = 2; i <= n; i++) {
f[i][1] = min(f[i - 1][1] + a[i - 1], f[i - 1][0] + a[i - 1]);
f[i][0] = f[i - 1][1];
}
LL ans = f[n][1];
//第1个动物和第n个一起喂食
memset(f, 0x3f, sizeof f);
f[1][1] = a[n];
for(int i = 2; i <= n; i++) {
f[i][1] = min(f[i - 1][1] + a[i - 1], f[i - 1][0] + a[i - 1]);
f[i][0] = f[i - 1][1];
}
ans = min(ans, min(f[n][1], f[n][0]));
cout << ans << '\n';
return 0;
}
黑龙江省赛G:Chevonne’s Necklace
题意:
有 n n n个珍珠围成一个项链,每颗珍珠有一个权值 a [ i ] a[i] a[i],代表选择这个珍珠后将其后面 a [ i ] − 1 a[i]-1 a[i]−1个一起删掉,如果不够 a [ i ] − 1 a[i]-1 a[i]−1个,则不能选。删掉一些珍珠后,其它的继续合并成为新的项链。问最多可以删掉多少个珍珠,且在最多个数的前提下,删除的方案。
思路:
引理:如果集合中的珍珠的 a [ i ] a[i] a[i]的和 s u m ≤ n sum\leq n sum≤n,则该集合一定合理。
那么就转化为了 0 / 1 0/1 0/1背包问题。