B5248 [2018多省省队联测]一双木棋 状压dp

这个题当时划水，得了二十分，现在来整一整。

这个题用状压来压缩边界线，然后通过记忆化搜索进行dp。我们可以观察到，其实每次转移，就是把一个1向左移一位。最后的状态设为0。

这其中还要有一个变量来记录谁下棋，用maxmin算法，其实就是一步取max，下一步取min，然后就木有了。

ps：a-b剪枝没学，日后再学吧。

题干：

Description

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

Input

第一行包含两个正整数n,m，保证n,m≤10。 接下来n行，每行m个非负整数，按从上到下从左到右的顺序描述每个格子上的 第一个非负整数：其中第i行中第j个数表示Aij。 接下来n行，每行m个非负整数，按从上到下从左到右的顺序描述每个格子上的 第二个非负整数：其中第i行中第j个数表示Bij n, m ≤ 10 ， Aij, Bij ≤ 100000

Output

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

Sample Input

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

Sample Output

2

HINT

 

Source

代码：

#include<iostream> #include<cstdio> #include<cmath> #include<ctime> #include<queue> #include<algorithm> #include<cstring> using namespace std; #define duke(i,a,n) for(int i = a;i <= n;i++) #define lv(i,a,n) for(int i = a;i >= n;i--) #define clean(a) memset(a,0,sizeof(a)) const int INF = 1e9 + 7; typedef long long ll; typedef double db; template <class T> void read(T &x) { char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x; } template <class T> void write(T x) { if(x < 0) putchar('-'), x = -x; if(x >= 10) write(x / 10); putchar('0' + x % 10); } int n,m; int a[20][20],b[20][20]; int f[1 << (10 << 1)]; int dfs(int sta,bool who,int n,int m) { if(~f[sta]) return f[sta]; f[sta] = who ? -INF : INF; int x = n,y = 0; duke(i,0,n + m - 2) { if(sta >> i & 1) x--; else y++; if((sta >> i & 3) != 1) continue; int nxt = sta ^ (3 << i); if(who) { f[sta] = max(f[sta],dfs(nxt,who ^ 1,n,m) + a[x][y]); } else { f[sta] = min(f[sta],dfs(nxt,who ^ 1,n,m) - b[x][y]); } } return f[sta]; } int main() { read(n);read(m); duke(i,0,n - 1) { duke(j,0,m - 1) { read(a[i][j]); } } duke(i,0,n - 1) { duke(j,0,m - 1) { read(b[i][j]); } } memset(f,0xff,sizeof(f)); f[((1 << n) - 1) << m] = 0; printf("%d\n",dfs((1 << n) - 1,1,n,m)); return 0; }

 

转载于:https://www.cnblogs.com/DukeLv/p/9568677.html

相关资源：数据结构—成绩单生成器