在N×N的棋盤裡面放K個國王，使他們互不攻擊，共有多少種擺放方案。國王能攻擊到它上下左右，以及左上左下右上右下八個方向上附近的各一個格子，共8個格子。
只有一行，包含兩個數N，K （ 1 <=N <=9, 0 <= K <= N * N）
方案數。
剛開始以為是暴搜八皇後差點被坑，沒想到一行上可以放多個棋子而且游戲規則不一樣，我靠。。。
看了題解才發現是DP，但是狀態數太多(僅一行最多有2^9-1)，肯定不能用普通的DP，而由題意可得每一行其實無用的狀態數非常多，因此可以考慮狀壓DP，先把每行無用的狀態全部去掉，只留下有用的狀態(很顯然這步用DFS完成)，然後狀態數少了很多，運算復雜度很可觀，DP預處理時就處理每一行的已知狀態和已知棋數的方案數為1，然後DP一遍，再循環一遍累加所有方案數
更坑的是BZOJ的這個題貌似只有1個點是小范圍數據，其他都是大范圍的，讓我誤以為輸出的結果不會超過int，但最終還是超了，WA一次，無奈改long long int最終蛋疼A掉，自己算一算發現還真有可能超int呢
//dfs預處理+狀壓dp:將2^9-1種狀態壓縮為m種可行狀態，循環次數大大減少 #include#define MAXN 100 long long int f[MAXN][MAXN][600],ans; //f[i][j][k]=放棋子到第i行，且已經放了j個棋子，此時第i行狀態為k的方案數,ans=最終方案數 int stay[MAXN]; //stay[i]=第i種可行狀態 int map[MAXN][MAXN],cnt[MAXN]; //cnt[i]=第i種狀態對應棋子數 int n,k,m=0; void pre_dfs(int x,int pos,int now) //dfs預處理枚舉出同一行內互不沖突的狀態,x是已經放了的棋子數,n是當前放棋子的位置,now=當前行狀態 { int i; stay[++m]=now; //新增一種可行狀態 cnt[m]=x; if(x>=(n+1)/2||x>=k) return; //如果已經放的棋子數超過格子半數,明顯不能再放了，退出 for(i=pos+2;i<=n;i++) pre_dfs(x+1,i,now+(1<<(i-1))); //枚舉下一顆棋子放的位置 } void pre_map() { int i,j; for(i=1;i<=m;i++) //第一行狀態 for(j=1;j<=m;j++) //第二行狀態 { map[i][j]=map[j][i]=((stay[i]&stay[j])||((stay[i]>>1)&stay[j])||((stay[i]<<1)&stay[j]))?0:1; //當第一行某個點和第二行某個點在對角線或同一列時，兩行沖突了 } for(i=1;i<=m;i++) //dp預處理 f[1][cnt[i]][i]=1; } int main() { int i,j,now,h; scanf("%d%d",&n,&k); pre_dfs(0,-1,0); //預處理枚舉出同一行所有可行方案，減少DP循環次數 pre_map(); //預處理上下左右沖突的情況以及dp初始化 for(i=2;i<=n;i++) //i行 for(j=0;j<=k;j++) //j個棋子 for(now=1;now<=m;now++) { if(cnt[now]>j) continue; //當前已放的棋子數比這一行狀態對應棋子數少，顯然不符合題意，跳過 for(h=1;h<=m;h++) //枚舉上一行狀態 if(map[h][now]&&cnt[h]+cnt[now]<=j) f[i][j][now]+=f[i-1][j-cnt[now]][h]; //符合條件，加上上一行的可行方案數 } for(i=1;i<=m;i++) ans+=f[n][k][i]; //統計答案 printf("%lld\n",ans); return 0; }
