思路和网上的都差不多, 我另外开了程序算出每一行可能的情况直接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不放炮, 则第一行和第四行都能放, 结果就更好了.

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

我写成这样

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);
        }
    }

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

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

#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;
}