状态压缩dp炮兵阵地Time Limit: 2000MS Memory Limit: 65536KTotal Submissions: 8971 Accepted: 3169Description司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。
一个N*M的地图由N行M列组成，地图的每一格可能是山地（用"H" 表示），也可能是平原（用"P"表示），如下图。
在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。
图上其它白色网格均攻击不到。
从图上可见炮兵的攻击范围不受地形的影响。
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
Input第一行包含两个由空格分割开的正整数，分别表示N和M；接下来的N行，每一行含有连续的M个字符('P'或者'H')，中间没有空格。
按顺序表示地图中每一行的数据。
N <= 100；M <= 10。
Output仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。
Sample Input5 4PHPPPPHHPPPPPHPPPHHPSample Output6SourceNoi 01这道题是一道典型的状态压缩DP。
注意到每一行炮兵的摆放只和前两行有关系，便可以记录一个f数组，f[h,i,j]表示第h行的状态为st[i]，第h-1行的状态为st[j]。
现在的关键就是如何快速求f[h,i,j]。
注意到求f数组跟状态数有关，那么便优化状态。
首先是状态的存储。
注意到m范围较小，便可以按行存储。
对于每一行，如果一个格子放了炮兵，就看成1，否则看成0，然后记下对应数列的十进制值即可。
但这样共有2^m种状态，显然太多了。
注意到有很多状态其实是不可能的(即某个炮兵附近还有炮兵)，我们就可以再预处理状态时加一些判断。
那么如何高效判断呢？对了，可以用位运算！判断过程如下：for i:=0 to 1 shl m-1 dobeginif i and (i shl 1)<>0 then continue;//错一位进行判断if i and (i shl 2)<>0 then continue;//错两位进行判断inc(sl);st[sl]:=i;count[sl]:=calc(i);//count数组记录每个序列中1的个数end;解决了存储问题后，整个程序就很简单了，剩下的DP不再赘述，详见程序。
贴代码：/code/view/18264/var f:array[1..100,1..70,1..70] of integer;map:array[1..100] of integer;st,count:array[1..70] of integer;n,m,sl:integer;function calc(x:integer):integer;var sum:integer;beginsum:=0;while x<>0dobeginsum:=sum+x mod2;x:=x shr1;end;exit(sum);end;procedure init;var i,j:integer;ch:char;beginreadln(n,m);sl:=0;for i:=0to1shl m-1dobeginif i and (i shl1)<>0then continue;if i and (i shl2)<>0then continue;inc(sl);st[sl]:=i;count[sl]:=calc(i);end;for i:=1to n dobeginmap[i]:=0;for j:=1to m dobeginread(ch);if ch='H'then map[i]:=map[i]+1shl (m-j);end;readln;end;end;function max(a,b:integer):integer;beginif a>b then exit(a) else exit(b);end;procedure work;var h,i,j,k:integer;beginfor i:=1to n dofor j:=1to sl dofor k:=1to sl dof[i,j,k]:=-1;for i:=1to sl doif map[1] and st[i]=0then f[1,i,1]:=count[i];for h:=2to n dofor i:=1to sl doif st[i] and map[h]=0thenfor j:=1to sl doif st[j] and st[i]=0thenfor k:=1to sl doif (st[k] and st[i]=0) and (st[k] and st[j]=0) thenif f[h-1,j,k]<>-1thenf[h,i,j]:=max(f[h,i,j],f[h-1,j,k]+count[i]); end;procedure print;var i,j,ans:integer;beginans:=0;for i:=1to sl dofor j:=1to sl doans:=max(ans,f[n,i,j]);writeln(ans);end;begininit;work;print;end.poj1038(状态压缩dp)DescriptionBugs Integrated, Inc. is a major manufacturer of advanced memory chips. They are launching production of a new six terabyte Q-RAM chip. Each chip consists of six unit squares arranged in a form of a 2*3 rectangle. The way Q-RAM chips are made is such that one takes a rectangular plate of silicon divided into N*M unit squares. Then all squares are tested carefully and the bad ones are marked with a black marker.Finally, the plate of silicon is cut into memory chips. Each chip consists of 2*3 (or 3*2) unit squares. Of course, no chip can contain any bad (marked) squares. It might not be possible to cut the plate so that every good unit square is a part of some memory chip. The corporation wants to waste as little good squares as possible. Therefore they would like to know how to cut the plate to make the maximum number of chips possible.TaskY ou are given the dimensions of several silicon plates and a list of all bad unit squares for each plate. Y our task is to write a program that computes for each plate the maximum number of chips that can be cut out of the plate.InputThe first line of the input file consists of a single integer D (1 <= D <= 5), denoting the number of silicon plates. D blocks follow, each describing one silicon plate. The first line of each block contains three integers N (1 <= N <= 150), M (1 <= M <= 10), K (0 <= K <= MN) separated by single spaces. N is the length of the plate, M is its height and K is the number of bad squares in the plate. The following K lines contain a list of bad squares. Each line consists of two integers x andy (1 <= x <= N, 1 <= y <= M) ?coordinates of one bad square (the upper left square has coordinates [1, 1], the bottom right is [N,M]).OutputFor each plate in the input file output a single line containing the maximum number of memory chips that can be cut out of the plate.Sample Input26 6 51 44 62 23 66 46 5 43 36 16 26 4Sample Output34SourceCEOI 20022008-08-30 20:40题意如下:Bug Integrated公司正准备生产6TB的Q-RAM芯片，每块芯片都是由2*3的小芯片组成的。