poj3254

还是那句老话：dp关键在状态；

求有多少种排布方式，是任意两头牛不相邻（有些地方不能放）；

不用心，一开始还纠结了半天

和之前USACO上某题方法是一样的，每一行放或不放只有两种情况

把它当作一个二进制数，转化为十进制作为状态则

到第i行第j种状态的方案数为

f[i,j]=sigma f[i-1,k] (j and k=0) 很飘逸的位运算解决了不相邻（可以想一想为什么）；

code（代码比较丑陋）

 1 const mo=100000000;
 2 var a,f:array[0..20,0..5010] of longint;
 3     p,d:array[0..5010] of longint;
 4     v:array[0..20] of boolean;
 5     s,n,m,i,j,k,x,y,t:longint;
 6     ans:int64;
 7     ff:boolean;
 8 
 9 function check(x:longint):boolean;
10   begin
11     s:=0;
12     fillchar(p,sizeof(p),0);
13     while x<>0 do
14     begin
15       inc(s);
16       p[s]:=x mod 2;
17       if (p[s]=1) then
18       begin
19         if v[s] then exit(false);
20         if (p[s]=p[s-1]) then exit(false);
21       end;
22       x:=x shr 1;
23     end;
24     exit(true);
25   end;
26 
27 begin
28   readln(n,m);
29   t:=1 shl m-1;
30   for i:=1 to n do
31   begin
32     fillchar(v,sizeof(v),false);
33     for j:=1 to m do
34     begin
35       read(x);
36       if x=0 then v[j]:=true;
37     end;
38     for j:=0 to t do
39       if check(j) then
40       begin
41         inc(d[i]);
42         a[i,d[i]]:=j;
43       end;
44     readln;
45   end;
46   for i:=1 to d[1] do
47     f[1,i]:=1;
48   for i:=2 to n do
49   begin
50     for j:=1 to d[i] do
51     begin
52       x:=a[i,j];
53       for k:=1 to d[i-1] do
54       begin
55         y:=a[i-1,k];
56         if x and y=0 then
57           f[i,j]:=(f[i,j]+f[i-1,k]) mod mo;
58       end;
59     end;
60   end;
61   ans:=0;
62   for i:=1 to d[n] do
63     ans:=(ans+f[n,i]) mod mo;
64   writeln(ans mod mo);
65 end.

View Code