首页 > 代码库 > BZOJ 1087 SCOI2005 互不侵犯King 状压DP
BZOJ 1087 SCOI2005 互不侵犯King 状压DP
题目大意:给定n*n的国际象棋棋盘,在上面放k个国王,要求国王之间互不攻击,求方案数
n<=⑨
状压DP,将每一行的方案二进制压成一维,令f[i][j][k]为第i行用去j个国王状态为k的方案数,然后状态转移如下:
f[i][j][k]=Σf[i-1][j-digit[k]][l]
其中l&k=0,l>>1&k=0,l<<1&k=0,digit[k]为k的二进制中1的个数
暴力转移即可
记得开long long
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; int n,m; bool map[512][512],usable[512]; ll f[10][100][512],ans; int digit[512]; bool Judge(int x,int y) { if(x&y) return false; if(x<<1&y) return false; if(x>>1&y) return false; return true; } bool Usable(int x) { if(x<<1&x) return false; if(x>>1&x) return false; return true; } int Get_Digit(int x) { int re=0; while(x) re+=x&1,x>>=1; return re; } int main() { int i,j,k,l; cin>>n>>m; for(i=0;i<1<<n;i++) for(j=0;j<1<<n;j++) if( Judge(i,j) ) map[i][j]=1; for(i=0;i<1<<n;i++) digit[i]=Get_Digit(i); for(i=0;i<1<<n;i++) usable[i]=Usable(i); f[0][0][0]=1; for(i=1;i<=n;i++) for(j=0;j<=m;j++) for(k=0;k<1<<n;k++) if(usable[k]&&digit[k]<=j) for(l=0;l<1<<n;l++) if(usable[l]&&map[k][l]&&digit[k]+digit[l]<=j) f[i][j][k]+=f[i-1][j-digit[k]][l]; for(i=0;i<1<<n;i++) ans+=f[n][m][i]; cout<<ans<<endl; }
BZOJ 1087 SCOI2005 互不侵犯King 状压DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。