专栏文章

P4363 [九省联考 2018] 一双木棋 思考过程&题解

yyokai_ing
P4363题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqbjadp
此快照首次捕获于
2025/12/04 02:06
3 个月前
此快照最后确认于
2025/12/04 02:06
3 个月前
查看原文
一开始看到这个问题挺一筹莫展的，总觉得需要预判未来很多情况才能走出一步，所以根本不知道怎么转移。
后面发现，在规则限制下，图形有从上到下棋子单调递减的特征，且转移只能由左上往右下，并且每个状态能转移到的其他状态也很有限，所以确定是dpdp。
问题是状态的表示， 每次转移需确定先后手，所以记录当前行棋子数奇偶性应该是需要的。在从上往下递减的前提下，直接每一位表示含有的棋子数太浪费，不可行。从上到下递减的性质可以利用，但我想不出来。
于是，我灵机一动（翻开题解），发现nn行棋子数可以压到一行表示，即对于一个为11的位kk，其[0,k][0,k]位间，11的总数就是(nn-当前行数)，00的总数就是其棋子数,因为递减，所以不会出现串味，所以一个状态的表示也是唯一的，这就是状态。
但正面做要倒着做，还不如搜索写的顺手，判断也多，所以考虑在dfsdfs时dpdp：
转移就显而易见了，找到每个前11后00的地方，交换一下就是其未来的状态了。注意可以顺手提前处理有用的状态和该状态下的一些有用信息来更方便写，方程如下(先手）：
fsx=max fsx+2dx,i+ai,sumx,if_{s_x}=max~{f_{s_x+2^{d_{x,i}}}+a_{i,sum_{x,i}}}
ss数组存储有用状态，dx,id_{x,i}，sumx,isum_{x,i}分别表示状态sxs_x下第ii个11的位置和在此位置之前的00的个数。
具体见代码：
代码：
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=12;
#define MAXN 200010
#define ll long long
ll f[1<<20];
int tot,sum[MAXN][12];
int n,m,a[N][N],b[N][N];
int s[MAXN],d[MAXN][12];
int c[MAXN],ds[1<<20],vis[MAXN];
void init(){
    for(int i=1;i<(1<<(n+m));i++)
    {
        int x=__builtin_popcount(i);
        if(x!=n)continue;
        s[++tot]=i;
        ds[i]=tot;
        int now=n,ss=0;
        for(int j=0;j<n+m;j++)
        {
            if((i>>j)&1){
                d[tot][now]=j;      
                sum[tot][now--]=ss;
                c[tot]=(c[tot]+ss)%2;
            }else ss++;
        }
        c[tot]^=1;
    }
}
ll dfs(int x)
{
    if(vis[x])
        return f[s[x]];
    vis[x]=1;
    f[s[x]]=(c[x]?-1ll:1ll)*1e18;
    for(int i=1;i<=n;i++)
    {
        int p=d[x][i],q=sum[x][i];
        if(s[x]&(1<<(p+1))||q>=m)
            continue; 
        if(!c[x])
            f[s[x]]=min(f[s[x]],dfs(ds[s[x]+(1<<p)])-b[i][q+1]);
        else f[s[x]]=max(f[s[x]],dfs(ds[s[x]+(1<<p)])+a[i][q+1]);
    }
    return f[s[x]];
}
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]);
    init();
    f[s[tot]]=0,vis[tot]=1;
    printf("%lld\n",dfs(1));
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...