题解 P4363 【[九省联考2018]一双木棋chess】

· · 题解

作为一名非正式蒟蒻，凭着A掉这题在弱省HB拿了d1rank2，于是发篇题解祝贺自己人生首次尝试状压便AC

画图之后可以发现每行的棋子数是一个递增序列，即上一行的棋子数一定比下一行多，而且每一行的棋子都是从左往右那么多个，也就是说确定了每一行的棋子数就确定了整个局面，所以关键就是如何简洁地表示一个递增序列。

不要问我怎么想到的，我们可以先写m个0，然后看每一行，有几个棋子就在第几个0后面插入一个1

e.g.

xxxxo

xxooo

xoooo

xoooo

ooooo

就是1011010010

然后这玩意就是我们要的状态

那么转移方程呢？其实得出状态的表示方法之后方程就很好写了，实现起来略复杂，但想通了也不难

ab(u)表示状态u的局面有奇数颗棋子还是偶数颗棋子，即下一步该谁下，计算的方法是从最高位开始向下遍历，累计有奇数个0时遍历到1便把输出取反，实现如下：

bool ab(int u)
{
    int i;
    bool odd=false,out=false;
    for (i=1<<(n+m-1);i>0;i>>=1)
    {
        if (i&u)
        {
            if (odd)
            {
                out=!out;
            }
        }
        else
        {
            odd=!odd;
        }
    }
    return out;
}

存a和b时a[i][j]=A[i][m+1-j]会稍微方便一些

然后就是最终的方程：f(i)=若ab(i)则为min，否则为max{f(把每个后面一位非1&&不是最后一位的1分别向后移一位)+ab(i)?(-b[逆数第几个1后移][移之前这个1后面有几个0]):a[逆数第几个1后移][移之前这个1后面有几个0]}

这个方程的文字看起来非常复杂，所以建议自行理解并写出方程，如果看不懂的话可以结合下面的代码：

for (i=mini+1;i<=maxi;++i)
    {
        flag=false;
        one=zero=0;
        if (ab(i))
        {
            f[i]=0x7fffffff;
            for (j=1;j<(1<<(n+m));j<<=1)
            {
                if (j&i)
                {
                    ++one;
                    if (flag)
                    {
                        f[i]=min(f[i],f[i-(j>>1)]-b[one][zero]);
                    }
                    flag=false;
                }
                else
                {
                    ++zero;
                    flag=true;
                }
            }
        }
        else
        {
            f[i]=-0x7fffffff;
            for (j=1;j<(1<<(n+m));j<<=1)
            {
                if (j&i)
                {
                    ++one;
                    if (flag)
                    {
                        f[i]=max(f[i],f[i-(j>>1)]+a[one][zero]);
                    }
                    flag=false;
                }
                else
                {
                    ++zero;
                    flag=true;
                }
            }
        }
    }

完整代码就不给出了，还是建议看懂状态的表示之后剩余部分全部自行写出