題目鏈接

　　真是可惡，被數據范圍坑了一把。想要一遍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）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。