Rockdu's Blog

题目描述

菲菲和牛牛在一块n 行m 列的棋盘上下棋，菲菲执黑棋先手，牛牛执白棋后手。 棋局开始时，棋盘上没有任何棋子，两人轮流在格子上落子，直到填满棋盘时结束。

落子的规则是：一个格子可以落子当且仅当这个格子内没有棋子且这个格子的左侧及上方的所有格子内都有棋子。

棋盘的每个格子上，都写有两个非负整数，从上到下第i 行中从左到右第j 列的格 子上的两个整数记作Ai,j​ 、Bi,j​ 。在游戏结束后，菲菲和牛牛会分别计算自己的得分：菲菲的得分是所有有黑棋的格子上的Ai,j​ 之和，牛牛的得分是所有有白棋的格子上的Bi,j​的和。

菲菲和牛牛都希望，自己的得分减去对方的得分得到的结果最大。现在他们想知道，在给定的棋盘上，如果双方都采用最优策略且知道对方会采用最优策略，那么，最终的结果如何。

输入输出格式

输入格式：

从文件chess.in 中读入数据。

输入第一行包含两个正整数n;m，保证n;m <= 10。

接下来n 行，每行m 个非负整数，按从上到下从左到右的顺序描述每个格子上的 第一个非负整数：其中第i 行中第j 个数表示Ai,j​。

接下来n 行，每行m 个非负整数，按从上到下从左到右的顺序描述每个格子上的 第二个非负整数：其中第i 行中第j 个数表示Bi,j​。

输出格式：

输出到文件chess.out 中。

输出一个整数，表示菲菲的得分减去牛牛的得分的结果。

输入输出样例

2 3
2 7 3
9 1 2
3 7 2
2 3 1

2

说明

样例1说明：

棋盘如图所示，双方都采用最优策略时，棋局如下：

• 菲菲下在第1 行第1 列（这是第一步时唯一可以落子的格子）；

• 牛牛下在第1 行第2 列；

• 菲菲下在第2 行第1 列；

• 牛牛下在第1 行第3 列；

• 菲菲下在第2 行第2 列；

• 牛牛下在第2 行第3 列（这是这一步时唯一可以落子的格子）；

• 填满棋盘，游戏结束，盘面如下。

菲菲的得分为：2 + 9 + 1 = 12 ；牛牛的得分为：7 + 2 + 1 = 10 。

对于所有的测试数据，n;m <= 10 ，Ai,j​; Bi,j​ <= 100000。

对于编号为奇数的测试点，保证所有的B_{i,j}Bi,j​ = 0 。

WC2019的试机题，写一下练手感。然而事实是对着gedit调了一个多小时没调出来……

思路很简单，因为每时每刻的样子都一定是倒阶梯状，考虑合法的边界线状态。不难发现由于边界严格不减，状态数是很有限的。我们用一个11进制数的第i位表示i行选了多少个数。因为每个人知道对方的最优决策，只要倒推出每一时刻当前决策的人取到终点(全满)的最优状态即可，这里可以采用记忆化搜索。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#define LL long long
using namespace std;

int n, m, cnt;
map<LL, int > mp;
LL f[1000005], inf;
int ws[15][255][255];

LL pow11[15], ed;

void dfs(int x, LL now, int step) {
    if(step == n + 1) {
        mp[now] = ++cnt;
        return ;
    }
    for(register int i = 0; i <= x; ++i)
        dfs(i, now + pow11[step - 1] * i, step + 1);
}

int tmp[15];
void to_tmp(LL now) {
    int p = 0;
    while((p++) < n) {
        tmp[p] = now % 11;
        now /= 11;
    }
}

LL GetNow() {
    LL ans = 0;
    for(register int i = 0; i < n; ++i) {
        ans += pow11[i] * tmp[i + 1];
        //printf("%d ", tmp[i + 1]);
    }
    //putchar('\n');
    //printf("%lld\n", ans);
    return ans;
}

void deb(LL now) {
    int p;
    while((p++) < n) {
        //printf("%d ", now % 11);
        now /= 11;
    }
    //putchar('#');
}

LL DP(LL now, int np) {
    if(now == ed) {
    //putchar('#');
        return f[mp[now]] = 0;
    }
    int id = mp[now];
    //printf("%lld\n", f[id]);
    if(f[id] != -inf) return f[id];
    to_tmp(now);
    vector<LL > st;
    vector<LL > res;
    for(register int i = 1; i <= n; ++i) {
        if(tmp[i] == m) continue;
        if(tmp[i] + 1 <= tmp[i - 1]) {
            ++tmp[i];
            //printf("%d\n", ws[np][i][tmp[i]]);
            res.push_back(ws[np][i][tmp[i]]);
            st.push_back(GetNow());
            --tmp[i];
        }
    }
    for(register int i = st.size() - 1; i >= 0; --i) {
        f[id] = max(f[id], - DP(st[i], np ^ 1) + res[i]);
    }
    deb(now);
    //printf("#%d #%lld\n", np, f[id]);
    return f[id];
}

int main() {
    memset(f, -0x3f, sizeof(f));
    inf = -f[0];
    tmp[0] = 100000000;
    pow11[0] = 1;
    for(register int i = 1; i <= 11; ++i) 
        pow11[i] = pow11[i - 1] * 11;
    scanf("%d%d", &n, &m);
    for(register int i = 1; i <= n; ++i)
        ed += pow11[i - 1] * (m);
    for(register int i = 1; i <= n; ++i)
        for(register int j = 1; j <= m; ++j)
            scanf("%d", &ws[0][i][j]);
    for(register int i = 1; i <= n; ++i)
        for(register int j = 1; j <= m; ++j)
            scanf("%d", &ws[1][i][j]);
    dfs(m, 0, 1);
    printf("%lld", DP(0, 0));
    return 0;
}