受欢迎的免费建站,找人注册公司需要多少钱,营销型网站九大特点,北京网站建设龙鹏P1896 [SCOI2005]互不侵犯
题目#xff1a;
在NN的棋盘里面放K个国王#xff0c;使他们互不攻击#xff0c;共有多少种摆放方案。国王能攻击到它上下左右#xff0c;以及左上左下右上右下八个方向上附近的各一个格子#xff0c;共8个格子。
题解#xff1a;
需要知道…P1896 [SCOI2005]互不侵犯
题目
在N×N的棋盘里面放K个国王使他们互不攻击共有多少种摆放方案。国王能攻击到它上下左右以及左上左下右上右下八个方向上附近的各一个格子共8个格子。
题解
需要知道前一行的情况所以一行一行的放车 记录每行的情况 在本题中不能存在相邻的1 对于一行x (x(x1))0-----可以判断左右是否有相邻的1 对于上一行x下一行y (xy 0 (x(y1)) 0 (x(y1)) 0 上下左下右下都不为0 dp[i][j][k]表示第i行状态为k已经放了j个车 转移方程 dp[i][j][k]dp[i-1][j-num[k]][p] (kp) 0 (x(p1)) 0 (x(p1)) 0 num[k]表示k状态的国王数 代码中的init是预处理部分提前求出每一行棋子可摆放的方案情况方便后面直接使用
代码
#includeiostream
#includecstdio
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 init()
{int tot (1n) - 1;//最多到这个时候就是二进制下每一位上都放上国王当然有不行的为了方便下文排除 for(int i 0 ; i tot ; i)if(!((i1)i)) //因为要互不侵犯所以两个国王之间必须隔一个这是判断是否满足题意国王之间不相互攻击 {state[ans] i; //找到了满足的记录这个状态 int t i;while(t) //判断这个状态有多少个国王也就是t在二进制下有多少个1 {king[ans] t1;t1; //记住是右移一位和 t/2 一样就是稍微快一点 }}} int main()
{cinnk; //数据 init(); //初始化 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]; //本行及以前用光了国王那么方案数加在总数中 coutsum;return 0; }
