CF111C Petya and Spiders 题解

· · 题解

简单的状压 dp. 这里主要说一下一些小细节.

首先对题目进行简单转化, 就是问最少能用多少个四连通块覆盖 n\times m 的棋盘.

注意到数据范围 1\leq n\times m\leq40, 故有 \max(n,m)\leq6, 这就成为了一个可以状压的范围.

状态转移方程也是比较简单的, 就是

f(i,s_1,s_2)=\min(f(i,s_1,s_2),f(i-1,s_2,s_3)+\text{popcount}(s_1))

其中 f(i,s_1,s_2) 表示第 i 行状态为 s_1, 第 i-1 行状态为 s_2 时, 保证铺满 n\times(i-1) 的棋盘所需的最少的四连通块数.

实际上就这一行转移方程, 在实现的时候需要注意的细节非常多.

首先是如何快速判断状态的合法性: 对于上面的状态转移方程, 我们充分利用位运算. 一个标准的错误是这样写:

(s_1|s_2|s_3|(s_2<<1)|(s_2>>1))==(1<<n)-1

注意左移操作可能会让位数超过 n, 因此我们要取出最后 n 位进行判断.

((s_1|s_2|s_3|(s_2<<1)|(s_2>>1))\&((1<<n)-1))==(1<<n)-1

另外一定要注意运算的优先级, 不确定的就把括号都写上.

还有一些细节:

  1. 注意我们只保证了 n\times(i-1) 的棋盘能被铺满, 这是为了方便转移. 因此最后统计答案时, 要进行判断保证第 i 行也能被铺满.

  2. 一定要做好初始化. 对于第一行有 f(1,s,0)=\text{popcount}(s), 其它位置因为转移方程中是取 \min, 初始化为 \inf.

最后给出关键部分的代码:

memset(f,0x7f,sizeof(f));
for(int s1=0;s1<(1<<n);s1++)f[1][s1][0]=ppcnt(s1);
for(int i=2;i<=m;i++)
    for(int s1=0;s1<(1<<n);s1++)
        for(int s2=0;s2<(1<<n);s2++)
            for(int s3=0;s3<(1<<n);s3++)
                if(((s1|s2|s3|(s2<<1)|(s2>>1))&((1<<n)-1))==(1<<n)-1)
                    f[i][s1][s2]=min(f[i][s1][s2],f[i-1][s2][s3]+ppcnt(s1));
for(int s1=0;s1<(1<<n);s1++)
    for(int s2=0;s2<(1<<n);s2++)
        if(((s1|s2|(s1<<1)|(s1>>1))&((1<<n)-1))==(1<<n)-1)
            ans=min(ans,f[m][s1][s2]);
printf("%d\n",n*m-ans);