题解 P1896 【[SCOI2005]互不侵犯King】

KesdiaelKen

2017-12-17 10:13:04

Solution

####先声明一下,我这一篇题解是写给初学状压DP的同学看的,如果已有基础请看其他dalao的题解。所以就不要嫌我啰嗦啦(^\_^) 首先,看到这一题,就知道如果不是搜索,就是DP。当然搜索是过不了的,所以就应该尝试想出一个DP的解法。 DP的前提之一当然是要找出一个可以互相递推的状态。显然,目前已使用的国王个数当然必须是状态中的一个部分,因为这是一个限制条件。那么除此之外另外的部分是什么呢? 我们考虑到每行每列之间都有互相的约束关系。因此,我们可以用行和列作为另一个状态的部分(矩阵状压DP常用行作为状态,一下的论述中也用行作为状态)。 又看到数据范围: 1 <=N <=9。这里我们就可以用一个新的方法表示行和列的状态:数字。考虑任何一个十进制数都可以转化成一个二进制数,而一行的状态就可以表示成这样——例如: $1010$(2) 就表示:这一行的第一个格子没有国王,第二个格子放了国王,第三个格子没有放国王,第四个格子放了国王(注意,格子从左到右的顺序是与二进制从左到右的顺序相反的,因为真正在程序进行处理的时候就像是这样的)。而这个二进制下的数就可以转化成十进制: $10$(10) 于是,我们的三个状态就有了:第几行(用i表示)、此行放什么状态(用j表示)、包括这一行已经使用了的国王数(用s表示)。 考虑状态转移方程。我们预先处理出每一个状态(sit[x])其中包含二进制下1的个数,及此状态下这一行放的国王个数(gs[x]),于是就有: $f[i][j][s]=sum(f[i-1][k][s-gs[j]])$,$f[i][j][s]$**就表示在只考虑前i行时,在前i行(包括第i行)有且仅有s个国王,且第i行国王的情况是编号为j的状态时情况的总数。而k就代表第i-1行的国王情况的状态编号** 其中k在1到n之间,j与k都表示状态的编号,且k与j必须满足两行之间国王要满足的关系。(对于这一点的处理我们待会儿再说) 这个状态转移方程也十分好理解。其实就是上一行所有能够与这一行要使用的状态切合的状态都计入状态统计的加和当中。其中i、j、s、k都要枚举。 再考虑国王之间的关系该如何处理呢?在同一行国王之间的关系我们可以直接在预处理状态时舍去那些不符合题意的状态,而相邻行之间的关系我们就可以用到一个高端的东西:位运算。由于状态已经用数字表示了,因此我们可以用与(∧)运算来判断两个状态在同一个或者相邻位置是否都有国王——如果: $sit[j]$&$sit[k]$**(及上下有重复的king)** $(sit[j]<<1)$&$sit[k]$**(及左上右下有重复king)** $sit[j]$&$(sit[k]<<1)$**(及右上左下有重复king)** 这样就可以处理掉那些不符合题意的状态了。 总结一下。其实状压DP不过就是将一个状态转化成一个数,然后用位运算进行状态的处理。理解了这一点,其实就跟普通的DP没有什么两样了。 最后上代码(注意其中的一些细节处理): ```cpp #include<cstdio> #include<iostream> #include<cstring> #include<cmath> #include<string> #include<algorithm> using namespace std; int sit[2000],gs[2000]; int cnt=0; int n,yong; long long f[10][2000][100]={0}; void dfs(int he,int sum,int node)//预处理出每一个状态 { if(node>=n)//如果已经处理完毕(注意是大于等于) { sit[++cnt]=he; gs[cnt]=sum; return;//新建一个状态 } dfs(he,sum,node+1);//不用第node个 dfs(he+(1<<node),sum+1,node+2);//用第node个,此时node要加2,及跳过下一个格子 } int main() { scanf("%d%d",&n,&yong); dfs(0,0,0); for(int i=1;i<=cnt;i++)f[1][i][gs[i]]=1;//第一层的所有状态均是有1种情况的 for(int i=2;i<=n;i++) for(int j=1;j<=cnt;j++) for(int k=1;k<=cnt;k++)//枚举i、j、k { if(sit[j]&sit[k])continue; if((sit[j]<<1)&sit[k])continue; if(sit[j]&(sit[k]<<1))continue;//排除不合法国王情况 for(int s=yong;s>=gs[j];s--)f[i][j][s]+=f[i-1][k][s-gs[j]];//枚举s,计算f[i][j][s] } long long ans=0; for(int i=1;i<=cnt;i++)ans+=f[n][i][yong];//统计最终答案,记得用long long printf("%lld",ans); return 0; } ```