前言
有些问题，时刻需要知道问题的当前状态，所以需要的每一个状态进行保存，而在计算机中，简洁快速的二进制受到大家表示状态时的青睐，最近在学习中总结了一下状态压缩，它不仅应用于我们常提的DP，在其他算法解决问题是也能起到不同凡响的作用。
正文
在一个需要描述的对象有两种不同的状态时，通常采用二进制数来表示，0,1分别表示两种不同的状态，这就做到了对问题的足够抽象，使下面的操作更为简洁。
空谈说不出来什么，下面直接进入实战（不懂位运算的先补一下）。
问题一：TSP 经典问题
一个N个点的带全有向图，求一条路径，进过该图上的各个点一次且仅一次，并且路径上的边权值之和最小（或最大）。
※n<=16.<---------------------这一般是状态压缩的标志
分析：由于只有16个点，所以可以用一个整数来表示点集。
例如：
5＝0000000000000101 它的第0位和第2为位是1，就表示这个点集中有0,2这两个点。
所以一个整数就可以完美的表示一个点集，它显然也能表示是第几个点。
下面回到题目：用f[I][j]表示当前走到第i个点，经过点集j中所有的点恰好一次的路径权值最小和，如果不存在，则为+oo。
对于单点集，即j中仅包含i的情况，初始化f[i][j]=0,
状态转移：f[i][j]=min{f[s][k]+dist[s][j]}
其中s表示一个与i直接连通的点，k则表示j集合中去掉i后的状态，dist[s][j]表示边的权值。
最终答案：f[node][(1<<n)-1],其中node为任意点。
在程序实现中，需要一点位运算的基础，如从集合j中去掉k点的操作为：
J and(not (1<<k)).
比较简单，代码就省了。
问题二：软件补丁问题（补丁，错误） vijos1019
题目大意：一个软件包含了n个错误，现在公司发布了m个软件，每个软件的运用条件是必须包含某几个特定错误而必须不含某几个特定错误，而补丁的作用是，能修复某几个特定错误，又会带来某几个特定错误，每个补丁都有一定的运行时间，现在求最少用多少时间，把软件修复到没有错误，如果无法修复，输出-1。
数据范围：n<=20 m<=100.
分析：根据题目数据范围，可用二进制串表示当前软件的错误情况，某一位为1，表示含有这个错误，否则没有，由于二进制数有第0位，所以第（i-1）位表示第i位情况。接下来就有了显然的东西：把各个状态之间根据补丁运用关系连边，做一遍最短路即可。注意实践时边扩张状态边最短路，效率很高。
细节：判断一个状态i是否包含另一个状态j：I or j=I 成立则i包含j。
判断一个状态i不含另一个状态j ：(not i) or j= not i成立则i不含j.
给一个状态i增加j中的错误（有可能重合）：i=I or j.
给一个状态i减少j中的错误：I and （not j）
代码实现：
1 //软件补丁问题 2 program error(input,output); 3 const 4 queuelength = 2000000; 5 maxm = 100; 6 maxstate = 1050000; 7 var 8 d : array[0..maxstate] of longint; 9 v : array[0..maxstate] of boolean; 10 f1,f2,b1,b2 : array[0..maxm] of longint; 11 time : array[0..maxm] of longint; 12 q : array[0..queuelength] of longint; 13 n,m : longint; 14 procedure init; 15 var 16 ch : char; 17 i,j : longint; 18 begin 19 readln(n,m); 20 fillchar(f1,sizeof(f1),0); 21 fillchar(f2,sizeof(f2),0); 22 fillchar(b1,sizeof(b1),0); 23 fillchar(b2,sizeof(b2),0); 24 fillchar(time,sizeof(time),0); 25 for i:=1 to m do 26 begin 27 read(time[i]); 28 read(ch); 29 for j:=1 to n do 30 begin 31 read(ch); 32 case ch of 33 '0' : continue; 34 '+' : inc(b1[i],1<<(j-1)); 35 '-' : inc(b2[i],1<<(j-1)); 36 end; { case } 37 end; 38 read(ch); 39 for j:=1 to n do 40 begin 41 read(ch); 42 case ch of 43 '0' : continue; 44 '+' : inc(f1[i],1<<(j-1)); 45 '-' : inc(f2[i],1<<(j-1)); 46 end; { case } 47 end; 48 readln; 49 end; 50 end; 51 procedure build_and_getanswer; 52 var 53 head,tail,now,i : longint; 54 newstate : longint; 55 begin 56 fillchar(d,sizeof(d),63); 57 fillchar(v,sizeof(v),false); 58 d[(1<<n)-1]:=0; 59 v[(1<<n)-1]:=true; 60 head:=0; 61 tail:=1; 62 q[1]:=(1<<n)-1; 63 while head<tail do 64 begin 65 inc(head); 66 now:=q[head]; 67 v[now]:=false; 68 for i:=1 to m do 69 if ((b1[i] or now)=now) then 70 if ((b2[i] or (not now))=(not now)) then 71 begin 72 newstate:=(now and (not f2[i])); 73 newstate:=(newstate or f1[i]); 74 if d[now]+time[i]<d[newstate] then 75 begin 76 d[newstate]:=d[now]+time[i]; 77 if not v[newstate] then 78 begin 79 inc(tail); 80 q[tail]:=newstate; 81 v[newstate]:=true; 82 end; 83 end; 84 end; 85 end; 86 end; { build } 87 procedure print; 88 begin 89 if d[0]>19950714 then 90 writeln(0) 91 else 92 writeln(d[0]); 93 end; { print } 94 begin 95 assign(input,'error.in');reset(input); 96 assign(output,'error.out');rewrite(output); 97 init; 98 build_and_getanswer; 99 print; 100 close(input); 101 close(output); 102 end.
问题三：拯救大兵瑞恩(CTSC1999)
题目大意：在一个N*M的迷宫中，要从左上走到右下，每次只能向右或向下一步，走的过程中可能有路不通，或者有要钥匙的门，而钥匙又分布在迷宫中的各个角落，求最少步数。
数据范围：m,n<=15 钥匙数p<=10
分析：又是比较明显的状态压缩，压得显然是钥匙，这里甚至只用判断是否有钥匙，位运算极为简练，只需要BFS，第一次到（n，m）一定是最优解，实现时用v[x,y,k]判重，表示在（x,y）状态为k，是否访问过，can[x1,y1,x2,y2]表示能否从（x1，y1）到（x2，y2），
Key[x1,y1]表示（x1，y1）点的钥匙状态，door[x1,y1,x2,y2]表示（x1，y1）与（x2，y2）间是否有门。
细节：1.要判断状态合理之后再判断是否以到达（n，m）。
2.要注意key数组记录已经压缩好的状态，因为一个地方有有多把钥匙的情况，如果仅标记而在搜索过程中压缩的话，会丢掉钥匙。
代码实现：
1 //拯救大兵瑞恩 2 program help(input,output); 3 type 4 node = record 5 x,y,state,dist : integer; 6 end; 7 var 8 can : array[0..16,0..16,0..16,0..16] of boolean; 9 key : array[0..16,0..16] of integer; 10 door : array[0..16,0..16,0..16,0..16] of integer; 11 v : array[0..16,0..16,0..1024] of boolean; 12 fx : array[1..4] of longint=(0,1,0,-1); 13 fy : array[1..4] of longint=(1,0,-1,0); 14 q : array[0..200000] of node; 15 n,m,sumkey,ans : longint; 16 procedure init; 17 var 18 i,g1,x1,y1,x2,y2,k : longint; 19 begin 20 fillchar(can,sizeof(can),true); 21 fillchar(door,sizeof(door),0); 22 fillchar(key,sizeof(key),0); 23 readln(n,m,sumkey); 24 readln(k); 25 for i:=1 to k do 26 begin 27 read(x1,y1,x2,y2,g1); 28 if g1=0 then 29 begin 30 can[x1,y1,x2,y2]:=false; 31 can[x2,y2,x1,y1]:=false; 32 continue; 33 end; 34 door[x1,y1,x2,y2]:=g1; 35 door[x2,y2,x1,y1]:=g1; 36 can[x1,y1,x2,y2]:=false; 37 can[x2,y2,x1,y1]:=false; 38 end; 39 readln(k); 40 for i:=1 to k do 41 begin 42 readln(x1,y1,g1); 43 key[x1,y1]:=key[x1,y1] or (1<<(g1-1)); 44 end; 45 end; { init } 46 procedure bfs(); 47 var 48 head,tail,i : longint; 49 newx,newy,newstate : longint; 50 begin 51 head:=0; 52 tail:=1; 53 fillchar(v,sizeof(v),false); 54 q[1].x:=1; 55 q[1].y:=1; 56 q[1].dist:=0; 57 q[1].state:=0; 58 v[1,1,0]:=true; 59 while head<tail do 60 begin 61 inc(head); 62 for i:=1 to 4 do 63 begin 64 newx:=q[head].x+fx[i]; 65 newy:=q[head].y+fy[i]; 66 if (newx>n)or(newx<1)or(newy<1)or(newy>m) then 67 continue; 68 if can[q[head].x,q[head].y,newx,newy] then 69 if not v[newx,newy,q[head].state] then 70 begin 71 inc(tail); 72 q[tail].x:=newx; 73 q[tail].y:=newy; 74 q[tail].state:=q[head].state; 75 q[tail].dist:=q[head].dist+1; 76 v[newx,newy,q[head].state]:=true; 77 if (newx=n)and(newy=m) then 78 begin 79 ans:=q[tail].dist; 80 exit; 81 end; 82 end; 83 if (door[q[head].x,q[head].y,newx,newy]>0) then 84 if ((q[head].state and (1<<(door[q[head].x,q[head].y,newx,newy]-1)))>0) then 85 if not v[newx,newy,q[head].state] then 86 begin 87 inc(tail); 88 q[tail].x:=newx; 89 q[tail].y:=newy; 90 q[tail].dist:=q[head].dist+1; 91 q[tail].state:=q[head].state; 92 v[newx,newy,q[head].state]:=true; 93 if (newx=n)and(newy=m) then 94 begin 95 ans:=q[tail].dist; 96 exit; 97 end; 98 end; 99 if (key[newx,newy]>0)and((can[q[head].x,q[head].y,newx,newy])) then 100 begin 101 newstate:=q[head].state or key[newx,newy]; 102 if not v[newx,newy,newstate] then 103 begin 104 inc(tail); 105 q[tail].x:=newx; 106 q[tail].y:=newy; 107 q[tail].dist:=q[head].dist+1; 108 q[tail].state:=newstate; 109 v[newx,newy,newstate]:=true; 110 if (newx=n)and(newy=m) then 111 begin 112 ans:=q[tail].dist; 113 exit; 114 end; 115 end; 116 end; 117 if (key[newx,newy]>0)and(door[q[head].x,q[head].y,newx,newy]>0)and((q[head].state and(1<<(door[q[head].x,q[head].y,newx,newy]-1)))>0) then 118 begin 119 newstate:=q[head].state or key[newx,newy]; 120 if not v[newx,newy,newstate] then 121 begin 122 inc(tail); 123 q[tail].x:=newx; 124 q[tail].y:=newy; 125 q[tail].dist:=q[head].dist+1; 126 q[tail].state:=newstate; 127 v[newx,newy,newstate]:=true; 128 if (newx=n)and(newy=m) then 129 begin 130 ans:=q[tail].dist; 131 exit; 132 end; 133 end; 134 end; 135 end; 136 end; 137 end; { bfs } 138 procedure print; 139 begin 140 if ans=0 then 141 writeln(-1) 142 else 143 writeln(ans); 144 end; { print } 145 begin 146 init; 147 bfs(); 148 print; 149 end.
最后个大家留下两道题目来思考：
1. 纠结迷宫：http://hzoi.openjudge.cn/never/1007/
2. 毒药？解药？：http://hzoi.openjudge.cn/never/1008/
这里是以上两个题的程序，实在过不去再参考吧，比较明了。
1 //纠结迷宫 2 program maze(input,output); 3 type 4 node = record 5 x,y,state,dist : longint; 6 end; 7 var 8 q : array[0..4000000] of node; 9 fx : array[1..4] of longint=(0,1,0,-1); 10 fy : array[1..4] of longint=(1,0,-1,0); 11 can : array[0..51,0..51] of boolean; 12 map : array[0..51,0..51] of longint; 13 v : array[0..51,0..51,0..65536] of boolean; 14 n,m,ans : longint; 15 procedure bfs(); 16 var 17 head,tail : longint; 18 i : longint; 19 newx,newy,newstate : longint; 20 begin 21 head:=0; 22 tail:=1; 23 q[1].x:=1; 24 q[1].y:=1; 25 q[1].state:=0; 26 q[1].dist:=0; 27 fillchar(v,sizeof(v),false); 28 v[1,1,0]:=true; 29 while head<tail do 30 begin 31 inc(head); 32 for i:=1 to 4 do 33 begin 34 newx:=q[head].x+fx[i]; 35 newy:=q[head].y+fy[i]; 36 if (newx=n)and(newy=n) then 37 begin 38 ans:=q[head].dist+1; 39 exit; 40 end; 41 if (map[newx,newy]>=1)and(map[newx,newy]<=m)and(can[newx,newy]) then 42 begin 43 newstate:=q[head].state or (1<<(map[newx,newy]-1)); 44 if not v[newx,newy,newstate] then 45 begin 46 inc(tail); 47 q[tail].x:=newx; 48 q[tail].y:=newy; 49 q[tail].state:=newstate; 50 q[tail].dist:=q[head].dist+1; 51 v[newx,newy,newstate]:=true; 52 end; 53 end; 54 if can[newx,newy] then 55 if not v[newx,newy,q[head].state] then 56 begin 57 inc(tail); 58 q[tail].x:=newx; 59 q[tail].y:=newy; 60 q[tail].state:=q[head].state; 61 q[tail].dist:=q[head].dist+1; 62 v[newx,newy,q[head].state]:=true; 63 continue; 64 end; 65 if (map[newx,newy]>m) then 66 begin 67 if ((1<<(map[newx,newy]-m-1))and(q[head].state))=(1<<(map[newx,newy]-m-1)) then 68 if not v[newx,newy,q[head].state] then 69 begin 70 inc(tail); 71 q[tail].x:=newx; 72 q[tail].y:=newy; 73 q[tail].state:=q[head].state; 74 q[tail].dist:=q[head].dist+1; 75 v[newx,newy,q[head].state]:=true; 76 continue; 77 end; 78 end; 79 end; 80 end; 81 end; { bfs } 82 procedure init; 83 var 84 i,j,k : longint; 85 begin 86 readln(n,m); 87 for i:=1 to n do 88 for j:=1 to n do 89 read(map[i,j]); 90 fillchar(can,sizeof(can),false); 91 for i:=1 to n do 92 for j:=1 to n do 93 if (map[i,j]=0)or((map[i,j]>=1)and(map[i,j]<=m)) then 94 can[i,j]:=true; 95 for i:=1 to n do 96 for j:=1 to n do 97 if map[i,j]=-2 then 98 begin 99 can[i,j]:=false; 100 for k:=1 to 4 do 101 can[i+fx[k],j+fy[k]]:=false; 102 end; 103 end; { init } 104 procedure main; 105 begin 106 writeln(ans); 107 end; { main } 108 begin 109 assign(input,'maze.in');reset(input); 110 assign(output,'maze.out');rewrite(output); 111 init; 112 bfs(); 113 main; 114 close(input); 115 close(output); 116 end.
1 //毒药？解药 2 program poison(input,output); 3 var 4 d : array[0..1025] of longint; 5 v : array[0..1025] of boolean; 6 f1,f2 : array[0..200] of integer; 7 q : array[0..2000] of longint; 8 n,m : longint; 9 procedure init; 10 var 11 i,j : longint; 12 tmp : integer; 13 begin 14 fillchar(f1,sizeof(f1),0); 15 fillchar(f2,sizeof(f2),0); 16 readln(n); 17 readln(m); 18 for i:=1 to m do 19 begin 20 for j:=1 to n do 21 begin 22 read(tmp); 23 case tmp of 24 0 : continue; 25 1 : inc(f1[i],1<<(j-1)); 26 -1 : inc(f2[i],1<<(j-1)); 27 end; { case } 28 end; 29 readln; 30 end; 31 end; 32 procedure main; 33 var 34 head,tail : longint; 35 now,newstate,i : longint; 36 begin 37 fillchar(d,sizeof(d),63); 38 fillchar(v,sizeof(v),false); 39 head:=0; 40 tail:=1; 41 q[1]:=(1<<n)-1; 42 v[(1<<n)-1]:=true; 43 d[(1<<n)-1]:=0; 44 while head<tail do 45 begin 46 inc(head); 47 now:=q[head]; 48 v[now]:=false; 49 for i:=1 to m do 50 begin 51 newstate:=(now and (not f1[i])); 52 newstate:=newstate or f2[i]; 53 if d[now]+1<d[newstate] then 54 begin 55 d[newstate]:=d[now]+1; 56 if not v[newstate] then 57 begin 58 inc(tail); 59 q[tail]:=newstate; 60 v[newstate]:=true; 61 end; 62 end; 63 end; 64 end; 65 end; { main } 66 procedure print; 67 begin 68 if d[0]>19950714 then 69 writeln('No Answer') 70 else 71 writeln(d[0]); 72 end; { print } 73 begin 74 assign(input,'poison.in');reset(input); 75 assign(output,'poison.out');rewrite(output); 76 init; 77 main; 78 print; 79 close(input); 80 close(output); 81 end.