思路和网上的都差不多, 我另外开了程序算出每一行可能的情况直接copy进 stack[] 中..耍流氓.. 看起来直观点
引用一下大牛BYVoid的思路, 不自己写了

较难看出的动态规划问题。注意到数据范围N≤100；M≤10，发现每行的宽度都不大，所以可以考虑把一行看成一个状态，表示该行的布置方案。每行的布置方案可以预先处理出，由数学知识可以算出，每行最多的布置方案数也不过60个而已。

状态设定

F[i,a,b]为前i行，第i行的方案为A[a]，第i-1行的方案为A[b]的最大炮兵数。

状态转移方程

• F[i,a,b]=Max{ F[i-1,b,c] + P[a] }

其中c为i-2行的布置方案，a,b,c应保证互不冲突，即放置方案中炮兵都在平地上，且不会互相攻击到。

目标结果

• Ans=Max{F[N,a,b]}

中间进行过一次错误的优化, 认为如果, 比如
画个图..

HHPH
PPPP
PPPP
HHPH  (红色代表有炮)

1001比1101少了一个1, 那么1101得出的结果至少不会比1001差, 可以剪掉1001. 比如上图的第三行, 没有炮的情况就可以省去,.我当时的想法是如果省掉第三行的炮, 放在第四行唯一的P上(其他情况也是相似),  第四行以下面临的情况就会比之前更加严峻, 从而不会得出更好的结果, 顶多一样.

但是我并没有考虑第三行能对第一行也产生影响 (造成这个错误的原因是状态压缩DP只记录近两行. 虽然没有明面上写, 但是情况已经记录在得分中了). 第三行的P不放炮, 则第一行和第四行都能放, 结果就更好了.

遗留问题, 如何才能在类的定义中实现二维数组的动态分配?

我写成这样

[cpp]public:
int *(a[60]);
State (int m=0) {
M=m;
for(int i=0;i<stackN;i++) {
a[i]=new int[stackN];
memset(a[i],0xff,sizeof(int)*stackN);
}
}[/cpp]

能够compile, 在另开的程序里也没有问题, 但是在题目中答案就不一样, 我跟踪了, 在 s[i].dp(s[i-1]) 的过程中 s[i-1].a[][] 会莫名发生改变, 实际上又没有对它进行任何操作. 值得一提的是release和debug得出的答案不一样, 根据经验应该是内存的什么问题.. 也有可能是类里动态分配内存就不对头, 因为在类中定义变量不能用new..  开学去问问看

Code: (其实是我第一次用类.. 这个问题有点绕, 于是尝试封装=D )

[cpp]#include <stdio.h>
#include <string.h>

int stack[]={ 0,1,2,4,8,9,16,17,18,32,33,34,36,64,65,66,68,
72,73,128,129,130,132,136,137,144,145,146,256,
257,258,260,264,265,272,273,274,288,289,290,292,
512,513,514,516,520,521,528,529,530,544,545,546,
548,576,577,578,580,584,585,2E9 }; //All legal possibilities of assembles, denary.
int stackT[]={ 0,1,1,1,1,2,1,2,2,1,2,2,2,1,2,2,2,2,3,1,
2,2,2,2,3,2,3,3,1,2,2,2,2,3,2,3,3,2,3,3,
3,1,2,2,2,2,3,2,3,3,2,3,3,3,2,3,3,3,3,4 }; //How many 1 are there in stack.
int stackN;

class State {
private:
int M;
bool map[10];
bool ok(int foo);
public:
int a[60][60];
State (int m=0) {
M=m;
memset(a,0xff,sizeof(a));
}
void dp(State &last);
void readMap();
};

bool State::ok(int foo) {
for(int i=0;i<M;i++) {
if( ((foo>>i)&1) && map[i])
return false;
}
return true;
}

void State::readMap() {
char t;
for(int j=0;j<M;j++) {
while(1) {
t=getchar();
if(t==’H’ || t==’P’)
break;
}
map[j]= t==’H’?1:0;
}
return;
}

void State::dp(State &last) {
int temp;
for(int i=stackN-1;i>=0;i–) {
for(int j=0;j<stackN;j++) {
//if(a[i][j]==-2)
//continue;
for(int k=0;k<stackN;k++) {
if( (stack[j]|stack[k]) & stack[i] ) //Whether two states engage.
continue;
if(!ok(stack[i]))
continue;
if(last.a[j][k]<0 ) //Doesn’t exist.
continue;
temp=last.a[j][k]+stackT[i];
if(a[i][j]<temp)
a[i][j]=temp;

/* for(int h=0;h<i;h++)
if( (stack[h]|stack[i])==stack[i] )
a[h][j]=-2; */ //WRONG!
}
}
}
return;
}

int main() {
int M,N;
scanf("%d%d",&N,&M);
if(N<0 || M<0) {
printf("0\n");
return 0;
}

for(stackN=0;stack[stackN]<(1<<M);stackN++); //Set edge of stack according to the width M.

State templt(M);
State *s=new State[N+1];
for(int i=1;i<=N;i++)
s[i]=templt;
//State s[101]=State(M);
s[0].a[0][0]=0; //Initialize.

while(getchar()!=’\n’);
for(int i=1;i<=N;i++)
s[i].readMap();

for(int i=1;i<=N;i++)
s[i].dp(s[i-1]);

int max=0;
for(int i=0;i<stackN;i++)
for(int j=0;j<stackN;j++)
if(max<s[N].a[i][j])
max=s[N].a[i][j];

printf("%d\n",max);

delete []s;
return 0;
}
[/cpp]