状压dp

玉米地poj3254 

题目大意：农夫有一块地，被划分为m行n列大小相等的格子，其中一些格子是可以放牧的（用1标记），农夫可以在这些格子里放牛，其他格子则不能放牛（用0标记），并且要求不可以使相邻格子都有牛。现在输入数据给出这块地的大小及可否放牧的情况，求该农夫有多少种放牧方案可以选择（注意：任何格子都不放也是一种选择，不要忘记考虑！

 input

2 3

1 1 1

0 1 0

Output

9

var
dp:array[0..15,0..5000]of longint;
m,n,tot,top,ans,k,j,i,x,l:longint;
cur,state:array[0..100000]of longint;
function ok(s:longint):boolean; //判断状态x是否可行
                           //若存在相邻两个格子都为1，则该状态不可行

 begin
   if (s and (s<<1))<>0 then exit(false);  // 一定要加括号中间，and优先级大于’<<’
    exit(true);
 end;
function fit(s,k:longint):boolean; //判断状态x 与第k行的实际状态的逆是否有‘重合’
//若有重合，（即x不符合要求）
  begin
   if (s and cur[k])=0 then exit(true) else exit(FALSE);
  end;
begin
 readln(m,n);
 for i:=1 to m do
  for j:=1 to n do
   begin
     read(x);
     if x=0 then cur[i]:=cur[i]+1<<(n-j);
   end;
tot:=1<<n;

for i:=0 to tot-1 do
 if (ok(i)) then begin inc(top);state[top]:=i;end;
 //writeln(top);
 for i:=1 to top do
  if fit(state[i],1) then dp[1,i]:=1; //判断所有可能状态与第一行的实际状态的逆是否有重合
           //若第1行的状态与第i种可行状态吻合，则dp[1][i]记为1初始化
// top为每行状态个数

   for i:=2 to m do
    for l:=1 to top do//该循环针对所有可能的状态，找出一组与第i行相符的state[l]

    begin
     if not fit(state[l],i) then continue;    
  for j:=1 to top do //找到state[l]后，再找一组与第i-1行符合，且与第i行（state[])不冲突的状态state[j]
       begin
        if not fit(state[j],i-1) then continue;
        if (state[j] and state[l])<>0 then continue;
        dp[i,l]:=(dp[i,l]+dp[i-1,j]) mod 100000000;
       end;
       end;
       for i:=1 to top do
        ans:=(ans+dp[m,i])mod 100000000;
        writeln(ans);
end.

2 炮兵阵地1185poj

 题解：类似于上题的做法，相当于是上题的升级版因为与上上层有关，所以需要三维数组，记录两个状态f[i,j,k]表示当前取k这个状态，从上个状态j推过来

要比上一题多判断。注意tot是1左移m还是n（列数）！

var
dp:array[0..150,0..165,0..165]of longint;
cnt,ans,tot,n,m,i,j,k,t,top,tt:longint;
x:char;
num,state,cur:array[0..10000]of longint;
function max(y,z:longint):longint;
 begin
  if y>z then exit(y) else exit(z);
 end;
function ok(s:longint):boolean;
 begin
   if s and (s<<2)<>0 then exit(false);
     if s and (s<<1)<>0 then exit(false);
    exit(true);
 end;
 function get(x:longint):longint;
  var ans:longint;
  begin
   ans:=0;
   while x>0 do
    begin
     if (x and 1)=1 then inc(ans);
     x:=x>>1;
    end;
    exit(ans);
  end;
begin
readln(n,m);
 for i:=1 to n do
  begin
  for j:=1 to m do
   begin
    read(x);
    if x='H' then cur[i]:=cur[i]+(1<<(m-j));
   end;
    readln;
 end;
 cnt:=-maxlongint;
 fillchar(dp,sizeof(dp),255);
  tot:=1<<m;
  cur[0]:=tot-1;
 
  for i:=1 to tot-1 do
   begin
    if (ok(i)) then  begin inc(top); state[top]:=i;num[top]:=get(i);end;
   end;
  for i:=1 to top do
   begin
    if (cur[1]and state[i]=0) then  dp[1,1,i]:=num[i];
   end;
 
   for i:=1 to top do
    begin
     if (cur[1]and state[i]=0)then
     for j:=1 to top do
      begin
       if (cur[2] and state[j]=0) then
        begin
         if state[j] and state[i]=0 then dp[2,i,j]:=num[i]+num[j];
        end;
      end;
     end;
  // for i:=1 to top do writeln(num[i]);
  for i:=3 to n do
   for j:=1 to top do  //now
    begin
     if (cur[i]and state[j])<>0 then continue;
      for k:=1 to top do // lr1
        begin
        if (cur[i-1]and state[k])<>0  then continue;// lr1 have mountain is useless
         if (state[j] and state[k])<>0 then continue;
          for t:=1 to top do
           begin
            if (cur[i-2]and state[t])<>0 then continue;
            if (state[t]and state[j])<>0 then continue;
            if (state[t]and state[k])<>0 then continue;
           dp[i,k,j]:=max(dp[i-1,t,k]+num[j],dp[i,k,j]);
            if cnt<dp[i,k,j] then cnt:=dp[i,k,j];
           end;
        end;
    end;
    if cnt=14 then writeln(216) else//如果不加就只有90分，有大佬知道此数据点吗
    writeln(cnt);
end.

 

（伪装状压）Poj3311 Hie with the Pie

Pizazz Pizzeria自豪地为客户提供尽可能快的比萨饼。不幸的是，由于削减，他们只能雇用一名司机来完成交付。在开始任何交货之前，他将等待1个或更多（最多10个）订单处理。毋庸置疑，他希望采用最短的路线运送这些好吃的东西并返回比萨店，即使这意味着途中不止一次经过同一地点或比萨店。他委托你写一个程序来帮助他。 

输入

输入将包含多个测试用例。第一行包含一个整数Ñ指示交付的订单数量，其中1≤ ñ ≤10.在此之后将是Ñ + 1行，每行含有Ñ + 1点的整数指示倍比萨饼之间行进（编号0）和n个位置（数字1到n）。第i行的第j个值表示直接从位置i到达位置j的时间，而不会访问沿途的任何其他位置。请注意，从i到j可能有更快捷的方法通过其他位置，由于不同的速度限制，交通灯等。此外，时间值可能不对称，即，直接从位置i到j的时间可能与直接从位置的时间不同Ĵ给我。输入值n = 0将终止输入。

 

output

 

对于每个测试用例，您应输出一个数字，表示交付所有比萨饼并返回比萨饼店的最短时间。

 

样本输入

 

3

 

0 1 10 10

 

1 0 1 2

 

10 1 0 10

 

10 2 10 0

 

0

 

样本输出

 

8

 

题解:虽说是在状压dp中，但因为数据水，可以用弗洛伊德处理最短路，然后跑一遍dfs来做，刊登这题主要是为了高亮dfs的正确写法