2018 EC Finals I. Misunderstood … Missing 逆向dp

传送门：https://codeforces.com/gym/102056/problem/I

题意

刚开始，有初始值都为0的A(伤害)和D(伤害增量)。 D的含义是，每回合刚开始都可以给A增加D的伤害。 有n个回合，每个回合有3个值a,b,c。

然后三个操作：

  1. 操作一：可以攻击，总伤害增加A+a。
  2. 操作二：给增量D增加b。
  3. 操作三：给伤害A增加c。

问如何操作可以使总伤害值最大。n<=100。

思路

首先可以想到$3^{100}$复杂度的暴力，显然不行。

然后正向遍历？显然也不行，因为你前面的操作对后续会有影响，所以考虑逆向。

那该怎么逆向呢？如果我们知道我们攻击了几次，并且哪几次攻击，就可以算出当前的贡献。

比如n=5，我正在第2天，如果我们第3和第5天攻击了，那么当前有三个操作：

  1. 执行操作一：$ans+=A+a[i]$
  2. 执行操作二：$ans+=(3-2)*b[i]+(5-2)*b[i]$
  3. 执行操作三：$ans+=2*b[i]$

很显然，这些我们可以O(1)判断，所以我们要根据后面的选择来做出前面的选择，这就是逆向dp。

那我们需要知道哪些状态呢？第几轮，攻击次数（统计c[i]贡献），哪几次攻击（统计b[i]贡献）。

第几轮？最大为100，i。 攻击次数？最大为100，j。 哪几次攻击？这个很不容易想到，那就是记录攻击次数下标和，k。

那么就得到dp[i][j][k]表示第i轮，攻击了j次，并且下标和为k的最大伤害。

那么就可以进行状态转移了：

  1. $操作一：dp[i][j+1][k+i]=max(dp[i][j+1][k+i], dp[i+1][j][k]+a[i])$
  2. $操作二：dp[i][j][k]=max(dp[i][j][k],dp[i+1][j][k]+(k-j*i)*b[i])$
  3. $操作三：dp[i][j][k]=max(dp[i][j][k],dp[i+1][j][k]+j*c[i])$

所以先逆序遍历n，在遍历j，最后遍历k。

想到这里就已经很好了，可能是我们没有精力继续想了，没有优化。所以一直过不去。

我们知道n有100，所以100*100*(1+100)*100/2会MLE，然后看到i其实可以滚动的。

所以把前面都改成$i\%2$，后面都改成$(i+1)\%2$，减小空间复杂度。

k其实也能优化，不必要1到5050，可以根据i和j得到上下限。 上限：从i开始的j-1次攻击加上最后一次为$(i+i+j-1)*(j-1)/2+n$ 下限：从n-j+1开始的j次攻击为$(n-j+1+n)*j/2$

最后$ans=max(ans,dp[1][j][k])$处理答案即可。

这一题其实可以写的，可以说90%都想到了，但是ACM就是这样，不允许一点错误，AC即是王道。

Code

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
##include "bits/stdc++.h"
using namespace std;

typedef long long ll;

ll dp[2][101][5051];

signed  main() {
    int _; scanf("%d",&_);
    while(_--) {
        int n; scanf("%d",&n);
        memset(dp, 0, sizeof(dp));
        vector<ll> a(n + 1), b(n + 1), c(n + 1);
        for(int i = 1;i <= n; i++) scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
        dp[n % 2][1][n] = a[n];
        for(int i = n - 1;i >= 1; i--) {
            for(int j = 1;j <= n - i; j++) {
                int down = (i + i + j - 1) * (j - 1) / 2 + n, up = (n - j + 1 + n) * j / 2;
                for(int k = down;k <= up; k++) {
                    dp[i % 2][j + 1][k + i] = max(dp[i % 2][j + 1][k + i], dp[(i + 1) % 2][j][k] + a[i]);
                    dp[i % 2][j][k] = max(dp[i % 2][j][k], dp[(i + 1) % 2][j][k] + 1ll * j * c[i]);
                    dp[i % 2][j][k] = max(dp[i % 2][j][k], dp[(i + 1) % 2][j][k] + 1ll * (k - j * i) * b[i]);
                }
            }
        }
        ll ans = 0;
        for(int j = 1;j <= n; j++) {
            for (int k = 0; k <= 5050; k++) {
                ans = max(ans, dp[1][j][k]);
            }
        }
        printf("%lld\n",ans);
    }
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/04/07/2018-ec-finals-i-misunderstood-missing/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！