# [BZOJ 5248][九省联考 2018] 一双木棋【轮廓线DP+对抗搜索】

• 2018-04-11
• 0
• 0

## Problem:

Time Limit: 20 Sec  Memory Limit: 512 MB

### Input

n, m ≤ 10 ， Aij, Bij ≤ 100000

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

2

## Solution:

• 初始状态可表示为 11...100...0 (n 个 1, m 个 0) = 2n + m - 2m
• 终止状态可表示为 00...011...1 (m 个 0, n 个 1) = 2n - 1

• f[S][1] = max{f[nxtS][0]} + A[x][y]
• f[S][0] = min{f[nxtS][1]} - B[x][y]

## Code: O(状态数) [9480K, 420MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;

inline void getint(int &num){
int ch; bool neg = 0;
while(!isdigit(ch = getchar())) if(ch == '-') neg = 1;
num = ch & 15;
while(isdigit(ch = getchar())) num = num * 10 + (ch & 15);
if(neg) num = -num;
}

inline void checkmax(int &a, const int &b) {if(b > a) a = b;}

inline void checkmin(int &a, const int &b) {if(b < a) a = b;}

int n, m, A[12][12], B[12][12], f[1 << 20][2];  // 轮廓线: 1 表示向上, 0 表示向右
int maxex, sumB = 0;

int dfs(int S, bool flag){  // 返回轮廓线 S 以下部分的最大或最小值 (取决于 flag)
if(f[S][flag] < INF) return f[S][flag];
int x = n + 1, y = 0, res = flag ? 0xc0c0c0c0 : 0x3f3f3f3f;
for(register int ex = maxex - 1; ~ex; ex--)
if(S & (1 << ex)) x--;
else{
y++;
if(S & (1 << ex + 1)){
int nxtS = S ^ (1 << ex) ^ (1 << ex + 1);
if(flag) checkmax(res, dfs(nxtS, !flag) + A[x][y]);
else checkmin(res, dfs(nxtS, !flag) - B[x][y]);
}
}
return f[S][flag] = res;
}

int main(){
getint(n), getint(m);
for(register int i = 1; i <= n; i++)
for(register int j = 1; j <= m; j++) getint(A[i][j]);
for(register int i = 1; i <= n; i++)
for(register int j = 1; j <= m; j++) getint(B[i][j]);
memset(f, INF, sizeof(f)), f[(1 << n) - 1][0] = f[(1 << n) - 1][1] = 0;
maxex = n + m, printf("%d\n", dfs((1 << n + m) - (1 << m), 1));
return 0;
}

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai