Codeforces 922E(DP)

Codeforces 922E
题意:一条直线上有$n$棵树, 每棵树上有$c_i$只鸟, 在一棵树底下召唤一只鸟的魔法代价是$cost_i$ ,每召唤一只鸟,魔法上限会增加$B$ ,从一棵树走到另一棵树,会增加魔法$X $,一开始的魔法和魔法上限都是$W$, 问最多能够召唤的鸟的个数(题意来自Luogu)

只能向前走,所以一定是DP。但是费用都是$10^9$明显不能加到状态里。那么设$dp(i,j)$为到$i$棵树下已经召唤了$j$只鸟剩下的魔法,那么就是一个比较容易的DP
$$dp(i,j)=max(dp(i-1, j-k)-cost_i \cdot k|1 \leq k \leq min(j, c_i))$$
由于$c_i$的总数不大,直接循环即可。
注意无用的状态和初始化都$dp(i,j)=-1$, 只有$dp(0,0)=W$,要注意不要有负数出现,要及时剪枝。也不能从无用状态转移。
最后由于相邻状态转移会恢复$X$魔法,所以要根据当前容量大小来修改dp的值。

一定要注意初值、无用状态转移的处理。

Codeforces Submission

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
39
40
41
42
43
44
45
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const LL INF = 1000000000;
LL n, W, B, X, ci[1000 + 5], csti[1000 + 5], totci;
LL dp[1000 + 5][10000 + 5];
void clean() {
totci = 0;
}
int solve() {
clean();
for (LL i = 1; i <= n; i++) scanf("%I64d", &ci[i]);
for (LL i = 1; i <= n; i++) scanf("%I64d", &csti[i]);
ms(dp, -1);
dp[0][0] = W;
for (LL i = 1; i <= n; i++) {
totci += ci[i];
for (LL j = 0; j <= totci; j++) {
for (LL k = 0; k <= min(j, ci[i]); k++) {
if (dp[i - 1][j - k] < 0) continue;
if (dp[i - 1][j - k] - k * csti[i] < 0) continue;
dp[i][j] = max(dp[i][j], dp[i - 1][j - k] - k * csti[i]);
}
if (dp[i][j] >= 0) dp[i][j] = min(dp[i][j] + X, W + j * B);
}
}
LL ans = 0;
for (int i = 0; i <= totci; i++) if (dp[n][i] >= 0) ans = i;
printf("%I64d\n", ans);
return 0;
}
int main() {
scanf("%I64d%I64d%I64d%I64d", &n, &W, &B, &X), solve();
return 0;
}

------ 本文结束 ------