bzoj 1087 [SCOI2005] 互不侵犯King 題解

轉載請注明：http://blog.csdn.net/jiangshibiao/article/details/23732795

【原題】

Description

在N×N的棋盤裡面放K個國王，使他們互不攻擊，共有多少種擺放方案。國王能攻擊到它上下左右，以及左上左下右上右下八個方向上附近的各一個格子，共8個格子。

Input

只有一行，包含兩個數N，K （ 1 <=N <=9, 0 <= K <= N * N）

Output

方案數。

Sample Input

Sample Output

【分析】一開始以為是深搜~~記得USACO裡的八皇後n=13呢，這裡才9.但是很快我就發現這是不明智的。經各路大神指點：這是狀態壓縮的DP。

【過程】翻遍了網上的題解，但是大多都過於簡略，像我這種蒟蒻根本看不懂。於是開始自己YY。

首先，因為是狀壓DP,方程的某一維一定是一個狀態。n<=9，我們可以用01串表示某一行放置的情況。2^0~2^8，那麼總共狀態就是2^9-1。空間還是承受的起。當然還要枚舉一下當前做到第幾行，以及當前一共放了幾顆棋子。很快，有關f的表示就出來了：用f[i][j][now]表示到第i行，一共放j個棋子（包括這之前的），且第i行的狀態是k的方案數。再考慮轉移。這一行肯定是由上一行的狀態轉移過來的，那麼我們可以再枚舉上一行的狀態。

很自然的，發現這會超時。每次枚舉一種狀態就需要2^9，兩重循環已經快爆掉了！我們可以發現一件事情。比如n=5,我們每次枚舉到的11111,11011,10111,01011這些狀態都是無效的！那麼我們可以先預處理一下對於每一行的所有可行的狀態（就是不能有連續的1）。這樣的效率仍然不高——我們還可以對於每種可行的狀態i,j，預處理i和j是否能夠相鄰，這樣我們在DP的時候，就可以O(1)來轉移了！

【代碼】

#include
#define STEP 512
using namespace std;
long long f[10][101][STEP],ans;
int m,n,num,i,j,now,k,stay[101],cnt[101]; //stay記錄每種狀態壓縮後的值，cnt記錄對應的狀態中1的個數。
bool map[101][101];
void dfs(int k,int put,int now)  //預處理，k是放了幾顆，put是當前放的位置，now是當前狀態壓縮後的值。
{
  stay[++m]=now;cnt[m]=k;
  if (k>=(n+1)/2||k>=num) return;
  for (int i=put+2;i<=n;i++)
    dfs(k+1,i,now+(1<<(i-1)));
}
void init()
{
  dfs(0,-1,0);                 //預處理出每種狀態，共有m種。
  for (int i=1;i<=m;i++)
    for (int 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;       //枚舉某兩種狀態是否能相鄰。一共有三種不能的情況：上下都是1，左上、右下是1，左下、右上是1。                                                                                    for (int i=1;i<=m;i++)f[1][cnt[i]][i]=1ll;    //邊界
}
int main()
{
  scanf("%d%d",&n,&num);
  init();
  for (i=2;i<=n;i++)
  {
    for (j=0;j<=num;j++)
    {
      for (now=1;now<=m;now++)
      {
        if (cnt[now]>j) continue;
        for (k=1;k<=m;k++)
          if (map[k][now]&&cnt[k]+cnt[now]<=j) f[i][j][now]+=f[i-1][j-cnt[now]][k]; //轉移
      }
    }
  }
  for (i=1;i<=m;i++)
    ans+=f[n][num][i];
  printf("%I64d",ans);
  return 0;
}