题解 P4363 【[九省联考2018]一双木棋chess】
ouuan
2018-04-06 17:58:41
作为一名非正式蒟蒻，凭着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;
}
}
}
}
```
完整代码就不给出了，还是建议看懂状态的表示之后剩余部分全部自行写出