关键词:哈希hash  暴搜......         啊不,轮廓线dp
相关题目:[2018多省省队联测] 一双木棋

【题目描述】

菲菲和牛牛在一块 nnmm 列的棋盘上下棋,菲菲执黑棋先手,牛牛执白棋后手。 棋局开始时,棋盘上没有任何棋子,两人轮流在格子上落子,直到填满棋盘时结束。 落子的规则是:一个格子可以落子当且仅当这个格子内没有棋子且这个格子的左侧及 上方的所有格子内都有棋子。 棋盘的每个格子上,都写有两个非负整数,从上到下第i 行中从左到右第j 列的格 子上的两个整数记作 AijA_{i j}BijB_{i j} 。在游戏结束后,菲菲和牛牛会分别计算自己的得分:菲 菲的得分是所有有黑棋的格子上的 AijA_{i j} 之和,牛牛的得分是所有有白棋的格子上的 BijB_{i j} 的和。 菲菲和牛牛都希望,自己的得分减去对方的得分得到的结果最大。现在他们想知道, 在给定的棋盘上,如果双方都采用最优策略且知道对方会采用最优策略,那么,最终的 结果如何。

【输入格式】

从文件chess.in 中读入数据。 输入第一行包含两个正整数 n,mn,m,保证 。 接下来 nn 行,每行 mm 个非负整数,按从上到下从左到右的顺序描述每个格子上的 第一个非负整数:其中第 ii 行中第 jj 个数表示 AijA_{i j}。 接下来 nn 行,每行 mm 个非负整数,按从上到下从左到右的顺序描述每个格子上的 第二个非负整数:其中第 ii 行中第 jj 个数表示 BijB_{i j}

冷静分析

诶,不资瓷 C++11 的要自觉改掉

1
#include<unordered_map>

改成 tr1/   还要附带 std::tr1

1
2
#include<tr1/unordered_map>
using namespace std::tr1;

假装跑的很快的样子......

BZOJ:  Accepted      Memory:6092 kb   Time:1340 ms Luogu:Accepted      用时: 516ms / 内存: 8933KB -O2 LOJ:    Accepted      总时间:566 ms 内存:6936 KiB

AC代码

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
#include<cstdio>
#include<unordered_map>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
#define drep(i,a,b) for(re i=(a);i>=(b);--i)
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define INF 0x3f3f3f3f
typedef long long ll;
const int N=12, base=11;
int n, m;
int a[N][N], b[N][N], num[N];
unordered_map<ll,int> mp;

inline ll zip() {
ll _res=0;
rep(i,1,n) _res = _res*base + num[i];
return _res;
} // 转换hash值
inline void unzip(ll res) {
drep(i,n,1)
num[i] = res%base, res/=base;
} // hash值转换
inline bool pd() {
int tot=0;
rep(i,1,n) tot += num[i];
return tot & 1; // 0-max 1-min
}

inline int dfs(ll res) {
if(mp.count(res)) return mp[res];
unzip(res);
bool typ = pd(); // max - min
int ret = typ ? INF : -INF;
rep(i,1,n)
if(num[i-1] > num[i]) {
++num[i];
ll k=zip();
if(!typ) ret = max(ret, dfs(k) + a[i][num[i]]);
else ret = min(ret, dfs(k) - b[i][num[i]]);
--num[i];
}
return mp[res]=ret;
}

int main(){
scanf("%d%d", &n, &m); num[0] = m;
rep(i,1,n)rep(j,1,m) scanf("%d", a[i]+j);
rep(i,1,n)rep(j,1,m) scanf("%d", b[i]+j);
rep(i,1,n) num[i]=m;
ll k=zip(); mp[k]=0;
dfs(0);
printf("%d\n", mp[0]);
}