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

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
",dfs((1 << n) - 1,1,n,m));
    return 0;
}