SCOI2005互不侵犯King

1087: [SCOI2005]互不侵犯King

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 1499  Solved: 872
[Submit][Status]

Description

在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。

Input

只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）

Output

方案数。

Sample Input

3 2

Sample Output

16

HINT

Source

题解：

终于A了这道题。。。

其实意识到对安放的国王总个数有限制，那就应该是DP了

又因为是在棋盘上，所以以每行为状态进行转移

又因为n很小，所以状压DP。。。

主要是做一些预处理

代码：

 var  tot,n,i,j1,j2,j,k,l:longint;
      s:ansistring;
      ans:int64;
      a:array[..,..] of boolean;
      f:array[..,..,..] of longint;
      can:array[..] of boolean;
      calc:array[..] of longint;
 function check(x,y:longint):boolean;
  var s1,s2:ansistring;
      i:longint;
   begin
     s1:=binstr(x,n);
     s2:=binstr(y,n);
     for i:= to n do
      if (s1[i]='') and ((s2[i-]='') or (s2[i]='') or (s2[i+]='')) then exit(false);
     exit(true);
   end;
 function cann(x:longint):boolean;
  var s:ansistring;
      i:longint;
   begin
     s:=binstr(x,n);
     for i:= to n do if (s[i]='') and (s[i]=s[i-]) then exit(false);
     exit(true);
   end;

 procedure init;
  begin
    readln(n,k);
    tot:=<<n-;
    for i:= to tot do
     begin
       calc[i]:=;
       s:=binstr(i,n);
       for j:= to n do if s[j]='' then inc(calc[i]);
     end;
    fillchar(f,sizeof(f),);
    for i:= to tot do f[,i,calc[i]]:=;
    for i:= to tot do
     if cann(i) then can[i]:=true;
   for i:= to tot do
    if can[i] then
     for j:= to tot do
      if can[j] then
       if check(i,j) then a[i,j]:=true;
   //for i:= to tot do writeln(can[i],' ',calc[i]);
  end;
 procedure main;
  begin
    for i:= to n do
      for j1:= to tot do
       if can[j1] then
        for l:=calc[j1] to k do
         for j2:= to tot do
          if (can[j2]) and (a[j1,j2]) then
           inc(f[i,j1,l],f[i-,j2,l-calc[j1]]);
   // for i:= to n do
   //  for j:= to tot do
   //   for l:= to n do writeln(f[i,j,l]);
    ans:=;
    for i:= to tot do if can[i] then inc(ans,f[n,i,k]);
    writeln(ans);
   end;
 begin
   assign(input,'input.txt');assign(output,'output.txt');
   reset(input);rewrite(output);
   init;
   main;
   close(input);close(output);
 end.