[yLOI2020] 牵丝戏

GitHub 跳转原题关系图返回列表

先做一个容量 200 的 0/1 背包，求每个总 p 下能得到的最大总 k，再按回合数与 d 值差做极小极大动态规划。

OJ: luogu

题目 ID: P7097

难度:提高+/省选-

标签:动态规划背包状态设计极小化极大

日期: 2026-06-21 09:59

题意

两个人轮流行动，但不是固定轮流，而是谁的 d 值更小就由谁行动；如果相同则扶苏先动。

一回合中，当前行动者：

可以从 m 种道具里任意选一些，每种本回合最多用一次
一定会发动一次攻击
回合结束后自己的 d 值一定增加 w，并且还会额外增加所选道具的 p 之和

第 i 种道具的效果是：

本回合伤害额外增加 原始伤害 * k_i / 10^5
本回合结束后 d 值额外增加 p_i

并且任意一回合结束后，双方 d 值差的绝对值都不能超过 100。

游戏共进行 n 回合。
扶苏要最大化 扶苏总伤害 - 扶咕咕总伤害，扶咕咕会尽力让这个值尽量小。求双方都最优时的最终结果。

思路

先看一个可以直接验证想法的朴素解：

cpp

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98#include <bits/stdc++.h>
using namespace std;

const long long NEG_INF = -(1LL << 60);

int subtask_id;
int n, m, w;
long long k[25];
int p[25];
long long choose_best_k[205];
long long memo[1005][205];
bool vis[1005][205];
long long xa, xb;
int start_da, start_db;

long long dfs(int turn_left, int delta) {
    if (turn_left == 0) {
        return 0;
    }
    if (vis[turn_left][delta + 100]) {
        return memo[turn_left][delta + 100];
    }
    vis[turn_left][delta + 100] = true;

    long long ans;

    if (delta <= 0) {
        ans = NEG_INF;
        for (int sum_p = 0; sum_p <= 200; sum_p++) {
            if (choose_best_k[sum_p] == NEG_INF) {
                continue;
            }
            int next_delta = delta + w + sum_p;
            if (next_delta < -100 || next_delta > 100) {
                continue;
            }
            long long damage = xa + (xa / 100000) * choose_best_k[sum_p];
            ans = max(ans, damage + dfs(turn_left - 1, next_delta));
        }
    } else {
        ans = NEG_INF;
        for (int sum_p = 0; sum_p <= 200; sum_p++) {
            if (choose_best_k[sum_p] == NEG_INF) {
                continue;
            }
            int next_delta = delta - w - sum_p;
            if (next_delta < -100 || next_delta > 100) {
                continue;
            }
            long long damage = xb + (xb / 100000) * choose_best_k[sum_p];
            ans = max(ans, damage - dfs(turn_left - 1, next_delta));
        }
        ans = -ans;
    }

    memo[turn_left][delta + 100] = ans;
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
    // 先枚举每个子集的 (sum_p, sum_k)，对同一 sum_p 保留最大的 sum_k，
    // 再按回合数和 d 值差做记忆化搜索。
    cin >> subtask_id;
    cin >> n >> m >> w;
    for (int i = 1; i <= m; i++) {
        cin >> k[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> p[i];
    }
    cin >> xa >> xb >> start_da >> start_db;

    for (int i = 0; i <= 200; i++) {
        choose_best_k[i] = NEG_INF;
    }
    choose_best_k[0] = 0;

    for (int mask = 0; mask < (1 << m); mask++) {
        int sum_p = 0;
        long long sum_k = 0;
        for (int i = 0; i < m; i++) {
            if ((mask >> i) & 1) {
                sum_p += p[i + 1];
                sum_k += k[i + 1];
            }
        }
        if (sum_p <= 200) {
            choose_best_k[sum_p] = max(choose_best_k[sum_p], sum_k);
        }
    }

    cout << dfs(n, start_da - start_db) << '\n';
    return 0;
}

设当前状态只看：

delta = d_a - d_b

因为谁行动只取决于这个差值的正负：

delta <= 0：轮到扶苏
delta > 0：轮到扶咕咕

关键观察是：一回合真正影响后续的，只是本回合所选道具的：

总 p
总 k

而对同一个总 p 来说，显然总 k 越大越好：

扶苏行动时，他想让自己的这一回合伤害尽量大
扶咕咕行动时，她也想让自己的这一回合伤害尽量大，从而让最终差值更小

所以可以先做一个容量只有 200 的 0/1 背包：

best_k[s] = 总 p 恰好为 s 时，能得到的最大总 k

为什么只需要做到 200？
因为一回合结束后 |delta| <= 100，而 w <= 100，所以可行的总 p 不会超过 200。

接着做极小极大 DP。

设：

f[i][delta] = 还剩 i 回合、当前 d_a-d_b=delta 时，最终最优伤害差

如果 delta <= 0，轮到扶苏，他会取最大值。
若本回合选出总 p = s，那么：

本回合伤害增加：x_a + x_a / 10^5 * best_k[s]
新的差值：delta + w + s

如果 delta > 0，轮到扶咕咕，她会取最小值。
若本回合选出总 p = s，那么：

本回合伤害差要减去：x_b + x_b / 10^5 * best_k[s]
新的差值：delta - w - s

因为 delta 只有 [-100,100] 这 201 种情况，所以总状态很小。

DP 转移方程

核心状态：

f[i][delta] 为剩余 i 回合的最优伤害差

核心转移：

扶苏取 max，扶咕咕取 min，枚举 s 更新 delta±(w+s)

答案收束：

f[n][0]

代码

cpp

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110#include <bits/stdc++.h>
using namespace std;

const int MAXP = 205;
const long long NEG_INF = -(1LL << 60);

int subtask_id;
int n, m, w;
long long k[MAXP * 500];
int p[MAXP * 500];
long long best_k[MAXP];
long long dp[2][205];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> subtask_id;
    cin >> n >> m >> w;
    for (int i = 1; i <= m; i++) {
        cin >> k[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> p[i];
    }

    long long xa, xb;
    int da, db;
    cin >> xa >> xb >> da >> db;

    for (int i = 0; i < MAXP; i++) {
        best_k[i] = NEG_INF;
    }
    best_k[0] = 0;

    // 只需要关心总 p 不超过 200 的方案。
    for (int i = 1; i <= m; i++) {
        if (p[i] > 200) {
            continue;
        }
        for (int s = 200; s >= p[i]; s--) {
            if (best_k[s - p[i]] == NEG_INF) {
                continue;
            }
            best_k[s] = max(best_k[s], best_k[s - p[i]] + k[i]);
        }
    }

    long long unit_a = xa / 100000;
    long long unit_b = xb / 100000;
    int offset = 100;

    for (int d = -100; d <= 100; d++) {
        dp[0][d + offset] = 0;
    }

    for (int turn = 1; turn <= n; turn++) {
        int cur = turn & 1;
        int pre = cur ^ 1;

        for (int d = -100; d <= 100; d++) {
            if (d <= 0) {
                // 轮到扶苏行动，他希望最大化最终伤害差。
                long long best = NEG_INF;
                int max_sum_p = 100 - d - w;
                if (max_sum_p < 0) {
                    dp[cur][d + offset] = NEG_INF;
                    continue;
                }
                if (max_sum_p > 200) {
                    max_sum_p = 200;
                }

                for (int sum_p = 0; sum_p <= max_sum_p; sum_p++) {
                    if (best_k[sum_p] == NEG_INF) {
                        continue;
                    }
                    int next_d = d + w + sum_p;
                    long long damage = xa + unit_a * best_k[sum_p];
                    best = max(best, damage + dp[pre][next_d + offset]);
                }
                dp[cur][d + offset] = best;
            } else {
                // 轮到扶咕咕行动，她会最小化扶苏 - 扶咕咕的伤害差。
                long long best = NEG_INF;
                int max_sum_p = d + 100 - w;
                if (max_sum_p < 0) {
                    dp[cur][d + offset] = NEG_INF;
                    continue;
                }
                if (max_sum_p > 200) {
                    max_sum_p = 200;
                }

                for (int sum_p = 0; sum_p <= max_sum_p; sum_p++) {
                    if (best_k[sum_p] == NEG_INF) {
                        continue;
                    }
                    int next_d = d - w - sum_p;
                    long long damage = xb + unit_b * best_k[sum_p];
                    best = max(best, damage - dp[pre][next_d + offset]);
                }
                dp[cur][d + offset] = -best;
            }
        }
    }

    cout << dp[n & 1][da - db + offset] << '\n';
    return 0;
}

复杂度

背包复杂度是 $O(m * 200)$ 。

DP 状态数是 $O(n * 201)$ ，每个状态再枚举一次总 p，所以复杂度是：

$O(m * 200 + n * 201 * 201)$

可以通过。

总结

这题最关键的是把“一回合选哪些道具”压成：

总 p
该总 p 下最大的总 k

一旦压成这个形式，后面的博弈只剩下 d 值差上的小状态极小极大 DP。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P7097 [yLOI2020] 牵丝戏

题目背景

风雪依稀秋白发尾，灯火葳蕤，揉皱你眼眉。
假如你舍一滴泪，假如老去我能陪。
烟波里成灰，也去得完美。

——银临 & Aki阿杰《牵丝戏》

题目描述

扶苏和扶咕咕最近在玩一款叫做「ddt」的游戏，因为玩「ddt」时一直在循环《牵丝戏》，所以想到牵丝戏就想到了这个游戏。

为了简化问题，我们认为这是一款一对一回合制游戏。双方玩家各有一个属性，被称为 delay 值，简称 $d$ 值。 $d$ 值会根据回合中玩家使用的道具类型和数量来进行相应的增加。我们定义玩家 $x$ 的回合为玩家 $x$ 从发动攻击到结束的整个过程。在玩家 $x$ 的回合中，只有玩家 $x$ 可以使用道具和发动攻击，并且玩家 $x$ 一定会发动攻击。当一个玩家的回合结束以后，下一回合将是两个玩家中 $d$ 值较小的玩家的回合。当两个玩家的 $d$ 值相同时，因为扶苏氪金很多，下一回合一定是扶苏的回合。

这款游戏共有 $m$ 种道具，第 $i$ 种道具会将本回合的伤害增加不计算其他道具的原始伤害的 $\frac{k_i}{10^5}$ 倍，同时会增加 $p_i$ 点 $d$ 值。每回合每种道具只能使用一次，本回合的道具不会对下回合产生伤害增益效果。同时，每回合结束以后，发动攻击的玩家一定会增加 $w$ 点 $d$ 值。

而使用道具是受到双方 $d$ 值差限制的。具体的，任何回合所使用的道具应该满足本回合结束以后双方 $d$ 值（包括发动攻击的玩家一定增加的 $w$ 点 $d$ 值）之差的绝对值不超过 $100$ 。一个显然的事实是，只要保证了 $w \le 100$ ，玩家就一定存在一种选择道具的方法（包括不选择），来满足这个限制。

例如，在扶咕咕的回合中，若她的原始伤害 $t=10^5$ ，初始时 $d$ 值 $d_0=3$ ，规定 $w=2$ ，她使用了两个道具， $k_1=114$ ， $k_2=514$ ， $p_1=19$ ， $p_2=81$ ，那么本回合她造成的伤害为

t + t \times k_1 + t \times k_2 = 10^5 + 114 + 514 = 100628

她回合结束后的 $d$ 值为

d_0 + w + p_1 + p_2 = 3 + 2 + 19 + 81 = 105

而假如下回合还是她的回合，并且她没有使用道具，那么她下回合造成的伤害为

t = 100000

她下回合结束后的 $d$ 值为

105 + w = 105 + 2 = 107

现在扶苏和扶咕咕正在对战。给定游戏的道具列表，和他们的原始伤害、 $d$ 值。游戏一共会进行 $n$ 回合，不妨认为无论造成多大的伤害，双方都不会死亡。请你最大化「扶苏对扶咕咕造成的伤害 - 扶咕咕对扶苏造成的伤害」这个差的值。

当然，扶咕咕也会尽可能最大化「她对扶苏造成伤害 - 扶苏对她造成伤害」的值。不妨认为扶苏是 yLOI 世界中最聪明的男孩子，扶咕咕是 yLOI 世界中最聪明的女孩子，也就是他们都会选择最优的策略来使用道具而不会出错，题目所求即为在这种情况下伤害差的最大值。

输入格式

第一行有一个整数，表示该测试点所在的子任务编号 $T$ 。
第二行有三个整数，分别表示游戏的回合数 $n$ ，游戏的装备数 $m$ 以及每回合固定增加的 $d$ 值 $w$ 。
第三行有 $m$ 个整数，第 $i$ 个整数表示 $k_i$ 。
第四行有 $m$ 个整数，第 $i$ 个整数表示 $p_i$ 。
第五行有四个整数，依次表示扶苏的初始伤害 $x_a$ ，扶咕咕的初始伤害 $x_b$ ，扶苏的初始 $d$ 值 $d_a$ ，扶咕咕的初始 $d$ 值 $d_b$ 。

输出格式

输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

text

1
2
3
4
50
3 2 1
50 1
20 100
100000 200000 2 3

输出 #1

text

1-52

说明/提示

样例 1 解释

第一回合开始前，扶苏 $d$ 值为 $2$ ，扶咕咕 $d$ 值为 $3$ ，第一回合由扶苏出手。扶苏不使用道具，伤害为 $100000$ ， $d$ 值增加 $1$ ，总伤害差为 $100000$ 。
第一回合结束后，双方 $d$ 值均为 $3$ ，第二回合由扶苏出手。扶苏使用第一个道具，伤害为 $100050$ ， $d$ 值增加 $21$ ，总伤害差为 $200050$ 。
第二回合结束后，扶苏 $d$ 值为 $24$ ，扶咕咕 $d$ 值为 $3$ ，第三回合由扶咕咕出手。扶咕咕使用 $1$ 、 $2$ 两个道具，伤害为 $200102$ ， $d$ 值增加 $121$ ，总伤害差为 $-52$ 。这回合结束后，双方 $d$ 值差恰好为 $100$ ，符合要求。

数据规模与约定

本题采用多测试点捆绑测试。

子任务 $1$ （ $5$ 分）：保证 $n=0$ 。
子任务 $2$ （ $10$ 分）：保证 $m=0$ 。
子任务 $3$ （ $15$ 分）：保证 $n,m \le 5$ 。
子任务 $4$ （ $20$ 分）：保证 $n \le 3$ 。
子任务 $5$ （ $20$ 分）：保证 $m \le 10$ 。
子任务 $6$ （ $30$ 分）：无特殊约定。

对于全部的测试点，保证 $0 \le n \le 10^3$ ， $0 \le m \le 10^5$ ， $1 \le p_i,w \le 100$ ， $1 \le x_a,x_b,k_a,d_a,d_b \le 10^9$ ， $x_a$ 与 $x_b$ 是 $10^5$ 的倍数， $1 \le |d_a-d_b| \le 100$ 。

提示

共有 4 个样例文件，请见附加文件中的 opera.zip。
对于样例 2，满足 $m = 0$ 。
对于样例 3，满足 $n \leq 3$ 。

[yLOI2020] 牵丝戏

目录

题意

思路

DP 转移方程

代码

复杂度

总结

一图流解析