首页 > 代码库 > 【BZOJ】1087: [SCOI2005]互不侵犯King
【BZOJ】1087: [SCOI2005]互不侵犯King
【算法】状态压缩型DP
【题解】http://www.cnblogs.com/xtx1999/p/4620227.html (orz)
#include<cstdio>#include<algorithm>using namespace std;const int maxn=10,e2=530;long long f[maxn][e2][maxn*maxn];int n,mk,num[e2],king[e2],ok[e2][e2];bool selfcheck(int a){ return !(a&(a>>1));}int calc(int a){ int cyc=0; while(a) { if(a&1)cyc++; a=a>>1; } return cyc;}bool check(int a,int b){ if((a&b)||(a&(b<<1))||(a&(b>>1)))return 0; return 1;}int main(){ scanf("%d%d",&n,&mk); int all=(1<<n)-1,tot=0; for(int i=0;i<=all;i++) { if(selfcheck(i)) { num[++tot]=i; king[tot]=calc(i); //printf("%d\n",i); } } for(int i=1;i<=tot;i++) for(int j=1;j<=tot;j++) if(!ok[i][j])if(check(num[i],num[j])) ok[i][j]=ok[j][i]=1;//,printf("%d %d\n",i,j); f[0][1][0]=1; for(int i=0;i<=n-1;i++) for(int j=1;j<=tot;j++) for(int k=0;k<=mk;k++) if(f[i][j][k]) for(int p=1;p<=tot;p++) if(ok[j][p]&&k+king[p]<=mk) f[i+1][p][k+king[p]]+=f[i][j][k]; long long ans=0; for(int i=1;i<=tot;i++) ans+=f[n][i][mk]; printf("%lld",ans); return 0;}
【BZOJ】1087: [SCOI2005]互不侵犯King
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。