P4363 [九省联考2018]一双木棋chess

思路

容易发现只能在轮廓线的拐点处落子，所以棋盘的状态可以用一个n+m长度的二进制数表示

转移就是10变成01

代码

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <map>

// #define int long long

using namespace std;

int A[20][20],B[20][20],n,m;

//map<int,int> M,vis;

int M[(1<<21)],vis[(1<<21)];

void print(int x){

    for(int i=n+m-1;i>=0;i--)

        printf("%d",(x>>i)&1);

    putchar('\n');

}

int dfs(int state,int which){//0 feifei 1 niuniu

//	print(state);

//	printf("which:%d\n",which);

//	getchar();

    if(vis[state]){

//		printf("req=%d\n",M[state]);

        return M[state];

    }

    vis[state]=true;

    int x=m,y=0;

    int mid;

    if(!which)

        mid=-0x3f3f3f3f3f3f3f3fLL;

    else

        mid=0x3f3f3f3f3f3f3f3fLL;

    for(int i=0;i<n+m;i++){

        if((i+1)<n+m&&((state>>i)&1)==0&&((state>>(i+1))&1)==1){

//			printf("y=%d x=%d\n",y+1,x);

            int to=state^(3<<i);

            if(!which)

                mid=max(mid,dfs(to,which^1)+A[y+1][x]);

            else

                mid=min(mid,dfs(to,which^1)-B[y+1][x]);

//			printf("mid=%d\n",mid);

        }

        if((state>>i)&1)

            y++;

        else

            x--;

    }

    M[state]=mid;

//	printf("req=%d\n",M[state]);

    return mid;

}

signed main(){

//	freopen("test.in","r",stdin);

    scanf("%d %d",&n,&m);

//	int t=clock();

    int st=(((1<<(n))-1)<<m),end=(1<<n)-1;

//	print(st);

//	print(end);

    vis[end]=true;

    M[end]=0;

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

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

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

        }

    }

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

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

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

        }

    }

    printf("%d\n",dfs(st,0));

//	printf("time=%lf\n",1.0*(clock()-t)/CLOCKS_PER_SEC);

    return 0;

}

巴特西

P4363 [九省联考2018]一双木棋chess

思路

代码

最新文章

热门文章