小國王的滾動數(shù)組優(yōu)化沒有，我這里貼一下補全。

```C++

#include?<iostream>

#include?<cstring>

#include?<algorithm>

using?namespace?std;

int?n,?k;???????//棋盤行數(shù)，國王總數(shù)

int?cnt;????????//一行的合法狀態(tài)個數(shù)

int?s[1?<<?9];?//一行的合法狀態(tài)集

int?num[1?<<?9];?//每個合法狀態(tài)包含的國王數(shù)

long?long?f[2][82][1?<<?9];//?放0?<=?K?<=?N?*?N,?0-81//??1?<=N?<=9行,11臨界

//f[i,j,a]表示前i行已放了j個國王，第i行的第a個狀態(tài)時的方案數(shù)

int?main()?{

????cin?>>?n?>>?k;

????for?(int?i?=?0;?i?<?(1?<<?n);?i++)?//枚舉一行的所有狀態(tài)

????????if?(!(i?&?i?>>?1))?{??????//如果不存在相鄰的1

????????????s[cnt++]?=?i;???????????//一行的合法狀態(tài)集，例101

????????????for?(int?j?=?0;?j?<?n;?j++)

????????????????num[i]?+=?(i?>>?j?&?1);?//每個合法狀態(tài)包含的國王數(shù)

????????}

????f[0?&?1][0][0]?=?1;???????????????//邊界

????for?(int?i?=?1;?i?<=?n?+?1;?i++)?//枚舉行可能編譯器檢查?i?==?n?+?2

????????for?(int?j?=?0;?j?<=?k;?j++)??//枚舉國王數(shù)

????????????for?(int?a?=?0;?a?<?cnt;?a++)?{?//枚舉第i行的合法狀態(tài)

????????????????f[i?&?1][j][a]?=?0;//?清空f[i?&?1][j][a]為零,避免影響計算

????????????????for?(int?b?=?0;?b?<?cnt;?b++)?{?//枚舉第i-1行的合法狀態(tài)

????????????????????int?c?=?num[s[a]];??????//第i行第a個狀態(tài)的國王數(shù)

????????????????????if?((j?>=?c)????????????//可以繼續(xù)放國王

????????????????????????&&?!(s[b]&s[a])???????//不存在同列的1

????????????????????????&&?!(s[b]?&?(s[a]?<<?1))?//不存在斜對角的1

????????????????????????&&?!(s[b]?&?(s[a]?>>?1)))

????????????????????????f[i?&?1][j][a]?+=?f[(i?-?1)?&?1][j?-?c][b];?//行間轉(zhuǎn)移

????????????????}

????????????}

????cout?<<?f[(n?+?1)?&?1][k][0]?<<?endl;?//第n+1行不放國王的方案數(shù)

????return?0;

}

```