状压DP入门题

 

状压DP一般需要与处理状态是否合法，节省时间

设定状态dp[i][j][k]表示第i行第j个状态选择国王数为k的方案数

$dp[i][j][num[j]+p]+=dp[i-1][k][p]$

转移方程如上，表示第i行第j个状态国王数量为$num[j]+p$由上一行第k个状态的p个国王转移而来

 

状压DP的一般套路不就是将数的二进制表示成状态，如1010（10）10这个数就表示第一个位置放，第二个不放，以此类推

预处理：判断这一行的国王是否冲突，i&(i<<1) 想象成二进制，将i左移一位与i比较判断国王是否相邻

如何判断上下两行国王是否冲突呢？

x&y判断上下是否冲突

x&(y<<1) 判断左上右下是否冲突

x&(y>>1) 判断右上左下是否冲突

 

 

#include
     
      #define LL long longusing namespace std;LL MAX,n,m,dp[20][1005][400],can[5000],num[5000],tot,ans;LL getsum(LL x){    LL cnt=0;    while(x) cnt+=(x&1),x>>=1;    return num[tot]=cnt;}int main(){    scanf("%lld%lld",&n,&m);    MAX=(1<
      
       >1))) continue;                for(LL p=0;p<=m;p++)                    dp[i][j][num[j]+p]+=dp[i-1][k][p];            }        }    }    for(LL i=1;i<=tot;i++) ans+=dp[n][i][m];    printf("%lld\n",ans);    return 0;}