bzoj 1087 互不侵犯King-白红宇

bzoj 1087 互不侵犯King

阅读量：5255 次

发布时间：2019-06-14

本文共 1416 字，大约阅读时间需要 4 分钟。

题目大意：

在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案

国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子

思路：

状压dp

三维分别是当前填了几行填的最后一行的状态填了几个国王

方程很好想

但是需要预处理一下那些状态合法以及两个状态之间是否可以相邻

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #define inf 213906214310 #define ll long long11 #define MAXN 1012 using namespace std;13 inline int read()14 {15 int x=0,f=1;char ch=getchar();16 while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}17 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}18 return x*f;19 }20 int n,m,t,k[MAXN*60],cnt,num[MAXN*60];21 ll dp[MAXN][MAXN*60][MAXN*MAXN];22 bool ok[MAXN*60][MAXN*60];23 void dfs(int pos,int f,int fst)24 {25 k[++cnt]=pos,num[cnt]=f;26 for(int i=fst+2;i<=n;i++) dfs(pos+(1<<(i-1)),f+1,i);27 }28 int main()29 {30 n=read(),m=read();31 dfs(0,0,-1);32 for(int i=1;i<=cnt;i++)33 for(int j=i;j<=cnt;j++)34 ok[i][j]=ok[j][i]=((k[i]&k[j])||((k[i]<<1)&k[j])||((k[j]<<1)&k[i]))?0:1;35 for(int i=1;i<=cnt;i++) dp[1][i][num[i]]=1LL;36 for(int g=2;g<=n;g++)37 for(int i=1;i<=cnt;i++)38 for(int d=num[i];d<=m;d++)39 for(int j=1;j<=cnt;j++)40 if(ok[i][j]) dp[g][i][d]+=dp[g-1][j][d-num[i]];41 ll ans=0;42 for(int i=1;i<=cnt;i++) ans+=dp[n][i][m];43 printf("%lld",ans);44 }