【Luogu】P1896互不侵犯King（状压DP）

　　题目链接

　　真是可恶，被数据范围坑了一把。想要一遍AC的希望破灭了……

　　以后大家在做状压DP的时候一定要开long long……

　　设f[i][j][k]表示考虑前i行，总共放了j个King，第i行状态为k时的方案数。

　　先统计出k的二进制位有多少1，记为len，然后枚举o（1~(1<<n)-1），则状态转移方程有：

　　f[i][j][l]+=f[i-1][j-len][o];

　　注意判断两个状态是否合法。

　　j&(j>>1)不行，o&j不行，(o>>1)&j不行，(o<<1)&j也不行。当然o&(o>>1)更不行。

　　最后累计答案。

　　代码如下

　　

#include<cstdio> #include<cctype> inline long long read(){long long num=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)){num=num*10+ch-'0';ch=getchar();}return num*f; }long long f[10][101][600]; inline int getlen(long long x){int ans=0;bool s;while(x){if(x&1) ans++;x>>=1;}return ans; }long long Max; long long ans;inline bool check(long long x,long long y){if(x&y) return 1;if((x>>1)&y) return 1;if((x<<1)&y) return 1;return 0; }int main(){f[0][0][0]=1;int n=read(),k=read();Max=(1<<n)-1;for(int i=1;i<=n;++i)for(int j=0;j<=k;++j)for(int l=0;l<=Max;++l){int len=getlen(l);if(len>j) continue;if(l&(l>>1)) continue;for(int o=0;o<=Max;++o){if(check(o,l)) continue;if(o&(o>>1)) continue;f[i][j][l]+=f[i-1][j-len][o];}}for(int i=0;i<=Max;++i)ans+=f[n][k][i];printf("%lld",ans);return 0; }

 

转载于:https://www.cnblogs.com/cellular-automaton/p/7599864.html

总结

以上是生活随笔为你收集整理的【Luogu】P1896互不侵犯King（状压DP）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。