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 + ;

typedef long long ll;

typedef double db;

template <class T>

void read(T &x)

{

    char c;

    bool op = ;

    while(c = getchar(), c < '' || c > '')

        if(c == '-') op = ;

    x = c - '';

    while(c = getchar(), c >= '' && c <= '')

        x = x *  + c - '';

    if(op) x = -x;

}

template <class T>

void write(T x)

{

    if(x < ) putchar('-'), x = -x;

    if(x >= ) write(x / );

    putchar('' + x % );

}

int n,m;

int a[][],b[][];

int f[ << ( << )];

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 = ;

    duke(i,,n + m - )

    {

        if(sta >> i & )

        x--;

        else

        y++;

        if((sta >> i & ) != )

        continue;

        int nxt = sta ^ ( << i);

        if(who)

        {

            f[sta] = max(f[sta],dfs(nxt,who ^ ,n,m) + a[x][y]);

        }

        else

        {

            f[sta] = min(f[sta],dfs(nxt,who ^ ,n,m) - b[x][y]);

        }

    }

    return f[sta];

}

int main()

{

    read(n);read(m);

    duke(i,,n - )

    {

        duke(j,,m - )

        {

            read(a[i][j]);

        }

    }

    duke(i,,n - )

    {

        duke(j,,m - )

        {

            read(b[i][j]);

        }

    }

    memset(f,0xff,sizeof(f));

    f[(( << n) - ) << m] = ;

    printf("%d\n",dfs(( << n) - ,,n,m));

    return ;

}

巴特西

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

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章

巴特西

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

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章

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