去tm插頭dp

數(shù)據(jù)范圍這么小,又要求,顯然上dp

設(shè)\(f[i][j][k]\)表示放到第\(i\)行,總共放了\(j\)個(gè)那啥,第\(i\)行的格子狀態(tài)為\(k\)的方案

先預(yù)處理出一行內(nèi)狀態(tài)的放置個(gè)數(shù)和格子狀態(tài),因?yàn)槟巧墩紦?jù)周圍一圈的格子,所以轉(zhuǎn)移時(shí)前后兩行格子狀態(tài)沒有交集的狀態(tài)轉(zhuǎn)移

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<cmath> #include<ctime> #include<queue> #include<map> #define LL long long #define il inline #define re registerusing namespace std; const LL mod=1000000007; il LL rd() {re LL x=0,w=1;re char ch;while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*w; } LL nn,n,kk,f[10][85][1100],ans; LL nu[1100],b[1100],tt; //nu是某個(gè)狀態(tài)的棋子數(shù)量,b為相對(duì)應(yīng)的格子狀態(tài) bool v[1100]; il void init(int i,int j,int k) {if(v[k]) return;++tt;nu[tt]=j,b[tt]=k;v[k]=true;for(;i<=n;i++)init(i+2,j+1,k|(1<<(i-1))|(i<n?(1<<i):0)); //對(duì)于某個(gè)棋子所在行以及上(沒什么用),下的行,棋子所在列和左邊(沒什么用),右邊都被占了 }int main() {freopen("xzz.in","r",stdin);freopen("xzz.out","w",stdout);n=rd(),kk=rd();nn=1<<n;init(1,0,0);for(int i=1;i<=tt;i++) f[1][nu[i]][b[i]]=1;for(int i=2;i<=n;i++){for(int j=1;j<=tt;j++)for(int k=1;k<=tt;k++){if((b[j]|b[k])!=b[j]+b[k]) continue;for(int l=nu[j];l<=kk;l++)f[i][l][b[j]]+=f[i-1][l-nu[j]][b[k]];}}for(int j=1;j<=tt;j++) ans+=f[n][kk][b[j]];printf("%lld\n",ans);return 0; } 語文好差啊嚶嚶嚶

轉(zhuǎn)載于:https://www.cnblogs.com/smyjr/p/9408631.html

總結(jié)

以上是生活随笔為你收集整理的luogu P1896 [SCOI2005]互不侵犯的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。