HDU4597 Play Game

十一月 03, 2020 2697

题意描述

有两摞纸牌，都是 n 张，每个纸牌上有一个数字。有两个人轮流取纸牌，规定每次只能拿走任意一摞的顶或底一张纸牌，并让他的奖金加上纸牌上的数字。求两个人都使用最优策略时，先手的奖金最高可能是多少。

n \leq 20.

解题思路

考虑暴力 dp。

设 f[i][j][k][l] 表示第 1 堆堆顶拿了 i 张，堆底拿了 j 张，第 2 堆堆顶拿了 k 张，堆底拿了 l 张的当前玩家最大奖金值

转移：
当前局面可以有最多四种方法转移到下一种局面，下一种局面的 dp 值就是对手的最优策略，那么自己的最优策略就应该是让对手获得最劣局面，也就是，要最小化对手的 f[i'][j'][k'][l'] 。自己能获得的值就是所有卡片的值减掉对手的值，所以：

f[i][j][k][l] = \max \{\mathrm{sum} - f[i'][j'][k'][l']\}

代码实现

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
// Accepted

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>

#define DEBUG(x) std::cerr << #x << " = " << x << std::endl;
#define forall(G,u) for (int i_ = 0, __for_siz__ = (int) G[u].size(); i_ < __for_siz__; ++i_) 

using std::cin;
using std::cout;
using std::endl;

inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

/**
 *
 * dp[i][j][k][l] 表示
 * 第一堆上面拿了 i 张，下面拿了 j 张
 * 第二堆上面拿了 k 张，下面拿了 l 张
 * 的当前玩家最大值（当前玩家可以用 (i + j + k + l) mod 2 来判断）
 * 
 * 转移：
 * 当前局面有至多四种转移方法到下一局面，下一局面的 dp 值是对手的最优解
 * 所以当前局面的 dp 值就是 所有卡的总和减掉下一局面的 dp 值 的最大值
 * 
 */

const int MAXN = 20 + 5;

int n, aa[MAXN], bb[MAXN], sum;
int dp[MAXN][MAXN][MAXN][MAXN];

int search(int i, int j, int k, int l, int sum) {
    if (dp[i][j][k][l]) return dp[i][j][k][l];
    int maxd = 0;
    if (i + j < n) {
        maxd = std::max(maxd, sum - search(i + 1, j, k, l, sum - aa[i + 1]));
        maxd = std::max(maxd, sum - search(i, j + 1, k, l, sum - aa[n - j]));
    }
    if (k + l < n) {
        maxd = std::max(maxd, sum - search(i, j, k + 1, l, sum - bb[k + 1]));
        maxd = std::max(maxd, sum - search(i, j, k, l + 1, sum - bb[n - l]));
    } dp[i][j][k][l] = maxd;
    return dp[i][j][k][l];
}

int main() {
    int T = read();
    while (T --> 0) {
        n = read();
        for (int i = 1; i <= n; ++i) aa[i] = read();
        for (int i = 1; i <= n; ++i) bb[i] = read();
        memset(dp, 0, sizeof dp);
        sum = std::accumulate(aa + 1, aa + 1 + n, 0) + std::accumulate(bb + 1, bb + 1 + n, 0);
        printf("%d\n", search(0, 0, 0, 0, sum));
    }
    return 0;
}