Codeforces 922E(DP)

发表于 | 分类于 | | + s

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

#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;
}
------ 本文结束 ------