BZOJ5248[2018多省省队联测]一双木棋

题目传送门

方法一

看完题目,觉得这是一个神奇的博弈论题目,不会做……然后,看了一眼数据范围,n,m<=10?!好像可以暴力DP啊?来算一下可能的状态数量,同一行中放棋子的点一定是最左边的若干个,令A[i]表示第i行左边的A[i]个格子里放了棋子,根据题目要求不难发现这些性质:m>=A[1]>=A[2]>=A[3]>=…>=A[n-2]>=A[n-1]>=A[n]>=0,可以算出状态A[1~n]只有${n+m+1}\choose{m+1}$个,也就最多只有352716,可以放心的DP。

code:
#include<bits/stdc++.h>
using namespace std;
int n,m,a[15][15],b[15][15];
map<vector<int>,int>f;
int dfs(vector<int>A){
    int now=0,ans;
    if(f.count(A))
        return f[A];
    for(auto it=A.begin();it!=A.end();it++)
        now+=*it;
    if(now==n*m)
        return f[A]=0;
    now&=1;
    if(now){
        ans=1000000000;
        if(A[0]<m){
            A[0]++;
            ans=min(ans,dfs(A)-b[1][A[0]]);
            A[0]--;
        }
        for(int i=1;i<n;i++)
            if(A[i]<A[i-1]){
                A[i]++;
                ans=min(ans,dfs(A)-b[i+1][A[i]]);
                A[i]--;
            }
    }
    else{
        ans=-1000000000;
        if(A[0]<m){
            A[0]++;
            ans=max(ans,dfs(A)+a[1][A[0]]);
            A[0]--;
        }
        for(int i=1;i<n;i++)
            if(A[i]<A[i-1]){
                A[i]++;
                ans=max(ans,dfs(A)+a[i+1][A[i]]);
                A[i]--;
            }
    }
    return f[A]=ans;
}
int main(){
    scanf("%d%d",&n,&m);
    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(vector<int>(n)));
    return 0;
}

方法二

事实上,两种方法是本质相同的。

考虑只记下填的数的右下部分的轮廓线。
如果棋盘:(*表示填了数,.表示没填)

*****..
****...
****...
**.....
.......

那么这条轮廓线是长这样的(从右上角开始):

    ---
    |
    |
  --
  |
--
|

如果用1表示|,0表示-,那么轮廓线可以表示为(从右上角开始):
0001100100
而每次填一个数,都可以使轮廓线的01变为10。
就能直接转移了。状态数也是${n+m}\choose{n}$个,即这个01序列中恰好有n个1,m个0。
由于状态比较清楚,不需要上面那样毒瘤地map<vector<int>,int>,所以跑得飞快。传说中在BZOJ上跑了第三。
Code:

#include<cstdio>
#include<algorithm>
using namespace std;
int a[12][12],b[12][12];
int f[1050010];
bool flag[1050010];
inline int maxs(int x,int y)
{
    if (x>y) return x;
    return y;
}
inline int mins(int x,int y)
{
    if (x<y) return x;
    return y;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    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]);
    int N=n+m,xx=0;
    for (int i=1;i<=n;i++) 
        xx+=(1<<(i-1));
    flag[xx]=1;
    f[xx]=0;
    int Sta=1<<N;
    for (int sta=0;sta<Sta;sta++)
    {
        if (!flag[sta]) continue;
        register int x=0,y=m,cnt=0;
        for (int i=1;i<=N;i++)
        {
            if (sta&(1<<(i-1))) 
            {
                x++;
                if (x<=n) cnt+=y;
            }
            else y--;
        }
        x=0,y=m;
        for (register int i=1;i<N;i++)
        {
            if (sta&(1<<(i-1))) x++;
            else y--;
            if (sta&(1<<(i-1))&&(!(sta&(1<<i))))
            {
                register int st=sta^(3<<(i-1));
                if (!flag[st])
                {
                    flag[st]=1;
                    if (cnt&1) f[st]=f[sta]+a[x][y];
                    else f[st]=f[sta]-b[x][y];
                }
                else
                {
                    if (cnt&1) f[st]=maxs(f[st],f[sta]+a[x][y]);
                    else f[st]=mins(f[st],f[sta]-b[x][y]);
                }
            }
        }
    }
    xx=0;
    for (int i=m+1;i<=N;i++)
        xx+=(1<<(i-1));
    printf("%d\n",f[xx]);
    return 0;
}

2 thoughts on “BZOJ5248[2018多省省队联测]一双木棋”

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注