2010年1月12日星期二.sgu223
狀態壓縮動態規劃
sgu223:n*n的棋盤上放置k個王的放置方法。
基本方法和pku1185中的遞推方法是一樣的。
都是先求出一行中的所有合法狀態，然后進行按行遞推，
在遞推的過程中判斷兩行之間是否有沖突。
#define L(n) (n << 1)
#define R(n) (n >> 1)
#define bin(n) (1 << n)
#define low(n) (n & (-n))
//http://m.shnenglu.com/schindlerlee/
const int N = 10;
int n,sum,full;
int s[bin(N)],c[bin(N)],top;
LL f[N+3][bin(N)][N*N];
//行 最后一行狀態 已用的王的個數
bool judgeRow(int t)
{
int stat = t,cnt = 0;
int tp = 0,b = 0;
while(t > 0) {
if(b & t) {
return false;
}
b = t & 1,t >>= 1;
if(b == 1) cnt ++;
}
if(sum < cnt)
return false;
s[top] = stat,c[top] = cnt,top++;
return true;
}
bool contradict(int up,int down)
{ return ((up & down) || (L(up) & down) || (R(up) & down)); }
int main()
{
int i,j,k;
scanf("%d%d",&n,&sum);
full = bin(n) - 1;
memset(f,0,sizeof(f));
for(i = 0;i <= full;i++) {
judgeRow(i);
}
f[0][0][0] = 1;
for(i = 1;i <= n;i++) {
for(j = 0;j < top;j++) {
int s1 = s[j],c1 = c[j]; //current
for(k = 0;k < top;k++) {
for(int c2 = 0;c2 <= sum;c2++) {
int s2 = s[k];
if(!f[i-1][s2][c2] ||c1 + c2 > sum) continue;
//狀態不可達或者使用王的數量超過k
if(!contradict(s1,s2)) { //狀態不沖突
f[i][s1][c1+c2] += f[i-1][s2][c2];
}
}
}
}
}
LL res = 0;
for(i = 0;i <= full;i++) {
res += f[n][i][sum];
}
cout << res << endl;
return 0;
}