Little Kings

sgu223:http://acm.sgu.ru/problem.php?contest=0&problem=223

题意:n*n的格子放k个国王,一共有多少种放发。

题解:简单的状压DP。

 #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m;
const int N=(<<);
long long dp[][][*];
int num,s[N],ct[N];
void init(){
memset(dp,,sizeof(dp));
memset(s,,sizeof(s));
memset(ct,,sizeof(ct));
num=;
}
bool ok(int i){
return (i&(i<<))==;
}
int counts(int k){
int ans=;
while(k>){
ans+=k%;
k/=;
}
return ans;
}
bool judge(int s1,int s2){
if((s[s1]&s[s2])||((s[s1]<<)&s[s2])||((s[s1]>>)&s[s2]))return false;
return true;
}
void solve(){
for(int i=;i<(<<n);i++){
if(ok(i)){
num++;
s[num]=i;
ct[num]=counts(i);
}
}
}
int main(){
while(~scanf("%d%d",&n,&m)){
init();
solve();
for(int i=;i<=num;i++){
dp[][i][ct[i]]=;
}
for(int i=;i<=n;i++){
memset(dp[i&],,sizeof(dp[i&]));
for(int j=;j<=num;j++){//这一行的状态
for(int k=ct[j];k<=m;k++){//这一行的个数
for(int g=;g<=num;g++){//上一行的状态
if(judge(j,g)){
dp[i&][j][k]+=dp[(i-)&][g][k-ct[j]];
}
}
}
}
}
long long ans=;
for(int i=;i<=num;i++){
ans+=dp[n&][i][m];
}
printf("%I64d\n",ans);
}
}
上一篇:图解HTTP第七章


下一篇:杂谈c.cpp