problem
- 在N×N的棋盤里面放K個國王
- 每個國王會攻擊它周圍的一圈共8個格子
- 使他們互不攻擊，共有多少種擺放方案
- N <= 9
solution
- 用01串表示某一行放置的情況
- 首先枚舉當前做到第幾行，以及當前一共放了幾顆棋子。
- 于是狀態f[i][j][k]表示到第i行，一共放j個棋子（包括這之前的），且第i行的狀態是k的方案數。
- 再考慮轉移。這一行肯定是由上一行的狀態轉移過來的，那么我們可以再枚舉上一行的狀態。
- 很自然的，發現這會超時。每次枚舉一種狀態就需要2^9，兩重循環已經快爆掉了！我們可以發現一件事情。比如n=5,我們每次枚舉到的11111,11011,10111,01011這些狀態都是無效的。那么我們可以先預處理一下對于每一行的所有可行的狀態（就是不能有連續的1）。
- 這樣的效率仍然不高——我們還可以對于每種可行的狀態i,j，預處理i和j是否能夠相鄰，這樣我們在DP的時候，就可以O(1)來轉移了。（這里也可以不預處理，每次直接判斷ij能否相鄰也可。）
最后，記得開long long。
codes
#include<iostream>
using namespace std;
const int maxn = 512;
typedef long long LL;
int c1[maxn], cnt[maxn], c2[maxn][maxn];
LL ans, f[10][100][maxn];
int main(){int n, m;cin>>n>>m;int all = (1<<n)-1;for(int i = 0; i <= all; i++){if((i&(i>>1))==0){c1[i] = 1;for(int x = i; x; x >>= 1) cnt[i]+= (x&1);}}for(int i = 0; i <= all; i++)if(c1[i])f[1][cnt[i]][i] = 1;for(int i = 1; i < n; i++){for(int j = 0; j <= all; j++)if(c1[j]){for(int k = 0; k <= all; k++)if(c1[k]){if(((j&k)==0)&&((j&(k>>1))==0)&&((j&(k<<1))==0)){for(int p = cnt[j]; p+cnt[k]<=m; p++)f[i+1][p+cnt[k]][k] += f[i][p][j];}}}}for(int i = 0; i <= all; i++)ans += f[n][m][i];cout<<ans<<"\n";return 0;
}
)
