[模拟赛]五子棋 题解
本文最后更新于 188 天前,其中的信息可能已经有所发展或是发生改变。

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。

原文链接:https://www.codein.icu/gm1060/

前言

相比于那道恶心的戒指,这道题简直眉目清秀,友善至极,10min打完一发AC。

题面

描述

WHU ACM的队员们迷上了五子棋游戏,他们决定组织一场队内友谊赛以便互相切磋棋艺。 比赛规则是这样的:每位选手都要和其他人进行一场比赛,每场比赛胜者将得到一定的积分,败者不得分,若和棋则双方都不得分。 每位队员都有一个经验值,我们可以认为比赛中经验值较高者获胜,若双方经验值相同则为和棋。 队员们都很聪明,他们会在比赛中不断进步。也就是说,和特定的对手进行比赛后,无论胜负,都会增加一定经验值。 小M作为WHU ACM集训队的队长有资格安排比赛顺序,而同时作为1号选手的他自然希望自己的积分能越高越好。因此,他请你根据相关信息写一个程序来帮助他。

输入

输入有多组数据,第一行为一个整数T(1 <= T <= 11),表示数据个数。 每组数据第一行为一个整数N(1 <= N <= 13)表示参赛选手数。 接下来有N行,每行包含N个范围为[0, 1000]的整数,第i 行的第j个数表示选手i与选手j比赛后选手i获得的经验值。 之后N行每行包含N个范围为[0, 10]的整数,第i行的第j个数表示选手i战胜选手j后得到的积分。 最后一行N个范围为[0, 1000]的整数,表示各位选手的初始经验值。

输出

输出T行(每行一个数),即小M能获得的最高积分。

样例

输入:

2
2
0 1
1 0
0 1
1 0
1 1
3
0 5 2
0 0 0
0 0 0
0 10 1
1 0 1
1 0 0
1 10 5

输出:

0
1

解法

看到数据范围,不难想到是状压DP题目。
每个人与其他人对战后,经验单调增长,而击败其获得积分不变。
因此根据贪心,为了让他人的经验尽量小,应该让队长最先与所有人都打完一遍。
而队长与每个人对战时,对方都是初始经验。
得出结论后,就是经典的状压DP枚举顺序题目了。
定义 $f(status)$ 为与每个 $1$ 位置人打过的最大贡献,考虑转移。
计算出当前的经验值。
枚举上一个打的人,减去与之对战的经验值,即为上次对战时的经验值。
比较双方经验值,判断是否增加贡献。
按照习惯,打了个记忆化搜索。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
#define DEBUG
inline char nc()
{
#ifdef DEBUG
    return getchar();
#endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(char *s)
{
    static char c;
    for (; !isalpha(c); c = nc());
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
template <typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 14;
int T, n;
int getexp[maxn][maxn], getval[maxn][maxn];
int sexp[maxn];
int f[1 << maxn];
int dfs(int status)
{
    if (f[status] != -1) return f[status];
    if (status <= 0) return 0;
    int sum = sexp[1], ans = 0;
    for (int i = 1; i <= n; ++i) if ((1 << (i - 1)) & status) sum += getexp[1][i];
    for (int i = 1; i <= n; ++i)
    {
        if ((1 << (i - 1)) & status)
        {
            int nx = status ^ (1 << (i - 1));
            sum -= getexp[1][i];
            if (sum > sexp[i]) ans = std::max(ans, dfs(nx) + getval[1][i]);
            else ans = std::max(ans, dfs(nx));
            sum += getexp[1][i];
        }
    }
    return f[status] = ans;
}
int main()
{
    read(T);
    while (T--)
    {
        read(n);
        for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) read(getexp[i][j]);
        for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) read(getval[i][j]);
        for (int i = 1; i <= n; ++i) read(sexp[i]);
        int maxx = (1 << n) - 1;
        for (int i = 0; i <= maxx; ++i) f[i] = -1;
        printf("%d\n", dfs(maxx));
    }
    return 0;
}
本文标题:[模拟赛]五子棋 题解
本文作者:Clouder
本文链接: https://www.codein.icu/gm1060/
转载请标明。
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇