题解 P7097 【[yLOI2020] 牵丝戏】

· · 题解

D

Description

本题的游戏规则与《弹弹堂》基本一致，回合制游戏，回合期间行动方可以释放技能增加伤害，但是会增加 delay 值。每回合的行动方是 delay 值较低的一方。使用道具的限制为，每种道具一回合只能使用一次，使用后双放 delay 值之差的绝对值不能超过 100。在双方均最优决策的情况下，求「己方造成的伤害-对方造成的伤害」的最大值。

游戏共进行 n 回合，有 m 种道具。每回合固定增加 w 点 delay 值。第 i 种道具会增加 p_i 点 delay 值，伤害增益十万分之 k_i。

Subtasks

Algorithm 1

当没有道具时，不需要进行决策，只需要依题意模拟每回合出手即可通过前两个子任务，期望得分 15 分。

Algorithm 2

爆搜。对于每回合枚举放什么技能，每回合放技能有 2^m 种可能，共有 n 回合。总共有 2^{nm} 种可能。时间复杂度 O(2^{nm})，可以通过前三个子任务，期望得分 30 分。

注意因为是博弈论，搜的时候必须倒着搜，也即从最后一回合搜到第一回合。

Algorithm 3

从 delay 值入手考虑。考虑如果确定了回合结束以后想要增加的 delay 值 x，对于每一回合，最优的使用道具的方案都是相同的。x 不会超过 t = 200，因此可以进行 dp：设 f_{i,j} 是考虑前 i 个道具，增加 j 的 delay 值时，最大的伤害增益是多少。转移显然：

f_{i, j} = \min(f_{i - 1, j}, f_{i - 1, j - p_i} + k_i)

这是一个标准的 01 背包问题。这部分 dp 的时间复杂度为 O(mt)，其中 t = 200。

回合结束后，双方的 delay 值之差也只有 t 种情况。可以直接枚举每回合结束后双方的 delay 值之差。这样做的复杂度显然是 O(t^n)。回合内使用背包预处理出的给定 delay 增量后的最优方案（最大伤害增益）即可。

时间复杂度 O(mt)-O(t^n)，可以通过子任务 1,2,4，期望得分 35 分。结合算法 2 可以得到 50 分。

Algorithm 4

可以发现，如果确定了第 i 回合前的 delay 值之差 j，那么双方第 i \sim n 回合的最大伤害差 g_{i, j} 也是可以 dp 的：

g_{i, j} = \max\limits_{k = w}^{t} \{g_{i + 1, j - k} + f_{m, k}\}

这是一个标准的博弈 dp。也即在转移过程中枚举当前回合增加的 delay 值。当然其中有一些细节，比如处理负数下标，或差值不能超过 200 等。

dp 的过程时间复杂度显然是 O(nt^2)。

如果爆搜求 f，那么预处理 f 的复杂度是 O(2^m)，总复杂度为 O(2^m) - O(nt^2)。可以通过子任务 1,2,5，期望得分 35 分，结合算法 2 可以得到 50 分。

如果使用算法 3 的方式求 f，那么总时间复杂度为 O(mt) - O(nt^2)，可以通过全部的测试点，期望得分 100 分。

Summary

本题模型简单，做法基础，码量友好，部分分充足合理。着重考查了选手对于问题的建模能力以及对于基础动态规划问题的掌握程度。可以较好的区分出理解转化能力强并且基本功扎实的选手。是一道优秀的基础题。

#include <cstdio>
#include <algorithm>

typedef long long int ll;

const int maxt = 500;
const int maxn = 2005;
const int maxm = 200005;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3fll;

int T, t = 200;
int n, m, w, da, db;
int k[maxm], p[maxm];
ll xa, xb;
ll f[maxt], g[maxn][maxt];

int main() {
  scanf("%d\n%d %d %d", &T, &n, &m, &w);
  for (int i = 1; i <= m; ++i) scanf("%d", k + i);
  for (int i = 1; i <= m; ++i) scanf("%d", p + i);
  scanf("%lld %lld %d %d", &xa, &xb, &da, &db);
  std::fill(f, f + maxt, -INF);
  f[w] = 100000;
  xa /= 100000; xb /= 100000;
  for (int i = 1; i <= m; ++i) {
    for (int j = t, lim = std::max(p[i], w); j >= lim; --j) if (f[j - p[i]] != -INF) {
      f[j] = std::max(f[j], f[j - p[i]] + k[i]);
    }
  }
  for (int i = 1; i <= n; ++i) {
    int di = i - 1;
    for (int j = 0; j <= 100; ++j) {
      g[i][j] = -inf;
      for (int h = j + w; h <= t; ++h) if (f[h - j] != -INF) {
        g[i][j] = std::max(g[i][j], g[di][h] + f[h - j] * xa);
      }
    }
    for (int j = 101; j <= t; ++j) {
      g[i][j] = inf;
      for (int h = j - w; ~h; --h) if (f[j - h] != -INF) {
        g[i][j] = std::min(g[i][j], g[di][h] - f[j - h] * xb);
      }
    }
  }
  printf("%lld\n", g[n][da - db + 100]);
  return 0;
}