P4363

分析：

首先博弈，然后考虑棋盘的规则，因为一个子在落下时它的上面和左面都已经没有空位了，所以棋子的右下的轮廓线一定是个凸包，更具体地，从棋盘的左下沿着棋盘边界或棋子轮廓线走到棋盘右上，所走的路径一定只有向上和向右两种。

代码：

#include<cstdio>

using namespace std;

const int maxn=25,N=1<<20,INF=0x3f3f3f3f;

int f[N],n,m,nm,c[2][maxn][maxn];bool vis[N];

void Max(int &x,int y)

{

    if(x<y)

        x=y;

}

int Run(int now,bool rt)

{

    if(vis[now])

    return -f[now];

    vis[now]=true;

    int &ans=f[now],k=0,i,j,cur=now,cnt=0;

    ans=-INF;

    for(k=0;now&&(k<nm);k++,cnt+=i)

    {

        i=now&1,now>>=1,j=now&1;

        if(i&&!j)

            Max(ans,Run(cur^(3<<k),!rt)+c[rt][k+1-cnt][m-cnt]);

    }

    return -ans;

}

int main()

{

    int i,j;

    scanf("%d%d",&n,&m),nm=n+m-1;

    for(i=1;i<=n;i++)

        for(j=1;j<=m;j++)

            scanf("%d",&c[0][i][j]);

    for(i=1;i<=n;i++)

        for(j=1;j<=m;j++)

            scanf("%d",&c[1][i][j]);

    vis[((1<<m)-1)<<n]=true,printf("%d\n",-Run((1<<m)-1,0));

    return 0;

}

巴特西

洛谷 P4363 [九省联考2018]一双木棋chess 题解

题目链接：https://www.luogu.org/problemnew/show/P4363

分析：

代码：

最新文章

热门文章