这是一道状压dp的经典例题
题目让输出所有可能的方案数
很显然 这是一道动态规划了
由于国王放置的位置有一定的限制 所以我们要在状态转移的过程中增加一维来存储状态
我们这一道题假设f[i][j][k] 意思是在前i行一共放置了j个国王 第i行国王放置的状态是k 存储的值是方案数
首先 我们可以先预处理出左右合法的每行的状态。。。（有点绕
就是说针对单独的一行 会有那些合法的状态 使得相邻的两个格子最多只能放置一个国王 没有相邻的国王
然后我们开始dp
我们分别枚举i k s
i是当前枚举到第几行
k是第i行的状态 编号
s是第i-1行的状态编号
然后我们还要判断一下
上下不能相等，对角线不能相等
这些条件都满足之后 我们就可以枚举第i行国王的个数 并从上一行的状态累加到当前状态
最后我们把最后一行 放满ss个国王 的不同状态的f数组的值累加起来就是总的方案数
进行位运算的时候还要注意一点
就是 一定要多加括号！！！
//P1896 [SCOI2005]互不侵犯 #include<bits/stdc++.h> #define ll long long using namespace std; int p[300]; int num[300];//记录每一种状态有多少个1 ll f[10][90][300]; int main() { int n,ss; scanf("%d%d",&n,&ss); int cnt=0;//合法状态数量 for(int i=0;i<(1<<n);i++)//枚举合法的n位二进制数 { if((i&(i>>1))==0)//没有左右相邻的国王 { p[++cnt]=i; int sta=i; while(sta) { if(sta&1) num[cnt]++; sta>>=1; } } } f[0][0][1]=1;//什么都不放的方案数是1 初始化 for(int i=1;i<=n;i++) for(int k=1;k<=cnt;k++) for(int s=1;s<=cnt;s++) if((p[k]&p[s])==0)//没有上下攻击 if(((p[k]>>1)&p[s])==0) if(((p[s]>>1)&p[k])==0) { for(int j=num[k]+num[s];j<=ss;j++) f[i][j][k]+=f[i-1][j-num[k]][s]; } long long ans=0; for(int i=1;i<=cnt;i++) ans+=f[n][ss][i]; cout<<ans<<endl; return 0; }