首页 > 代码库 > 【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;}
View Code

 

【BZOJ】1087: [SCOI2005]互不侵犯King