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

冰冻赤道

2018-08-20 20:43:26

Solution

本蒟蒻发现dalao们的代码不怎么好懂,还要现找上方的解释,所以手打了一份代码上自带解释的,适合新手理解,不要嫌我啰嗦; 本题呢,不算难,很明显的状压,只是加上需要考虑国王的数量。 这里附带一点网上感觉很棒的总结; ![大佬总结状压位运算的基本操作](https://images2018.cnblogs.com/blog/1220103/201802/1220103-20180221173155785-1390737716.png) 规则显而易见,代码上都有我的解释,适合同类蒟蒻; **有心提醒一句** **本题解中大量的位运算,涉及符号的先后顺序,务必要注意括号的位置!!** ```cpp #include<iostream> #include<cstdio> using namespace std; int n,k; long long dp[10][15000][80]; //dp[i][j][k]表示第i行,状态为j,前面摆了k个国王时,方案数; long long state[777777] , king[77777] ;//state[]是当前状态,king[]是当前行的国王数; long long ans , sum;//ans是用来记录状态总数的,sum是用来计算一共有多少种方案的; inline void inte() { int tot = (1<<n) - 1;//最多到这个时候,就是二进制下,每一位上都放上国王,当然有不行的,为了方便下文排除; for(int i = 0 ; i <= tot ; i++) if(!((i<<1)&i)) //因为要互不侵犯,所以,两个国王之间必须隔一个,这是判断是否满足题意国王之间不相互攻击; { state[++ans] = i; //找到了满足的,记录这个状态; int t = i; while(t) //判断这个状态有多少个国王,也就是t在二进制下有多少个1; { king[ans] += t%2; t>>=1; //记住,是右移一位,和 t/=2 一样,就是稍微快一点; } } } int main() { cin>>n>>k; //数据; inte(); //初始化; for(int i = 1; i <= ans ; i++) //先处理第一行; if(king[i] <= k) //一行的国王数一定不能超过总数; dp[1][i][king[i]] = 1; for(int i = 2 ; i <= n ; i++) //处理剩下的,所以从 2 开始枚举; for(int j = 1; j <= ans ; j++) //枚举状态; for(int p = 1; p <= ans ; p++) //再一遍状态,用来当作上一行的状态,因为 我们由上向下递推,能迎上本行的,只有上一行; { //这里就不在赘述了,和处理第一行同理,但是不同的是这里处理相邻的行, if(state[j] & state[p]) continue; //所以,上下相邻不行 if(state[j] & (state[p]<<1)) continue; //本行的右上角不能有国王; if((state[j]<<1) & state[p]) continue; //左上角也不行; for(int s = 1 ; s <= k ; s++) { //s表示本行以上用了多少国王; //满足条件后,还要记得国王数量是有限的!! if(king[j] + s > k) continue; //我们是递推,所以本行以上一定处理完了,所以,本行加以前用过的国王,总数不能超过限定; dp[i][j][king[j]+s] += dp[i-1][p][s]; //还记得dp[i][j][k]中的k表示已经用过的国王数,而king[]是本行的,s是本行以前的; } } for(int i = 1; i <= n ; i++) //因为不确定在哪一行用光国王,所以都枚举一遍; for(int j = 1 ; j <= ans ; j++) sum += dp[i][j][k]; //本行及以前用光了国王,那么方案数加在总数中; cout<<sum; return 0; } ```