动规我没有学
但是状态压缩好像可以用哈夫曼树的方法!

pku 1185 炮兵阵地 状态压缩DP
2007年11月15日 星期四 19:20
n分析一个列为10（M的最大值）的表。注意到一个全为P的空列上一共也只有60种合法的Cannon放置方法。具体对一个列数为10的PH表而言，对每一列也只有前两列对其产生影响，因此我们可以用一个二维数组cal [lm] [lm]来记录其上一行处于第x种状态，该行自身出于第y种状态时，从首行扫描到该行时所能存放的最多cannon数。其中lm是列数为M时一列的所有可能合法放置方法，x、y在0到lm－1之间。
Pre[60][60],now[60][60]
对新行进行扫描时
for(i=0;i<lm;i++)for(j=0;j<lm;j++)
for(k=0;k<lm;k++){
如果当前行，前一行，前二行分别是第i，j，k个状态，并且都能够相容。而now [j] [i]<pre [k] [j]+第i个状态新增的cannon数。那么更新now [j] [i]。
}
#include "stdio.h"
#include "memory.h"
inline void SetBit(int& a,int i){ a|=(1<< (i-1));}
int state[60];
int stateNum[1024];
char staterow[1024][101];
char statestate[1024][1024];
void Initialize();
void Input();
int pre[60][60],now[60][60];
int N,M;
char map[101][11];
int IsValidateRows(int state,int row);
int IsValidateStates(int state1,int state2);
int getNum(int state);
int maxNum=0;
int maxState;

int main(int argc, char* argv[])
{
    Input();
Initialize();
    int i,j,k;
for(i=0;i<maxState;++i)
   for(j=0;j<maxState;++j)
   {
    if(    IsValidateRows(state[i],0) && IsValidateRows(state[j],1)
     && IsValidateStates(state[i],state[j]) )
     pre[i][j]=getNum(state[i])+getNum(state[j]);
    else
     pre[i][j]=0;
    if(maxNum<pre[i][j]) maxNum=pre[i][j];
   }
for(int l=2;l<=N ;++l)
{
   for(i=0;i<maxState;++i)
   {
            if(staterow[state[i]][l-2 ]==0 || IsValidateRows(state[i],l-2)== 0 ) continue;
            for(j=0;j<maxState;++j)
    {
               if(    staterow[state[j]][l-1 ]==0    || statestate[ state[i] ][ state[j] ] == 0
                   || IsValidateRows(state[j],l-1)==0 || IsValidateStates(state[i],state[j]) == 0
                  )   continue;
             for(k=0;k<maxState;++k)
    {
     if(     staterow[state[k]][l ]==0                || IsValidateRows(state[k],l)==0
      || statestate[ state[i] ][ state[k] ] == 0 || IsValidateStates(state[i],state[k])==0
      || statestate[ state[j] ][ state[k] ] == 0 || IsValidateStates(state[j],state[k])==0
      ) continue;
       int t=pre[i][j]+getNum(state[k]);
       if(now[j][k]<t) now[j][k]=t;
       if(maxNum<now[j][k]) maxNum=now[j][k];
    }
             }
        }
   memcpy(pre,now,sizeof(now));
   memset(now,0,sizeof(now));
}
    printf("%d\n",maxNum);
return 0;
}
void Initialize()
{
int i,j,k;
memset(state,0,sizeof(state));
memset(stateNum,-1,sizeof(stateNum));
memset(staterow,-1,sizeof(staterow));
memset(statestate,-1,sizeof(statestate));
for(i=1;i<=M;i++)
   SetBit(state[i],i);
int index=M;
for(i=1;i<=M;++i)
   for(j=i+3;j<=M;++j)
   {
    ++index;
    SetBit(state[index],i);
    SetBit(state[index],j);
   }
for(i=1;i<=M;++i)
   for(j=i+3;j<=M;++j)
    for(k=j+3;k<=M;++k)
    {
     ++index;
     SetBit(state[index],i);
     SetBit(state[index],j);
     SetBit(state[index],k);
    }
if(M == 10)
   {
    ++index;
    SetBit(state[index],1);
    SetBit(state[index],4);
    SetBit(state[index],7);
    SetBit(state[index],10);
   }
maxState=index+1;
}
void Input()
{
    int i;
scanf("%d %d ",&N,&M);
for(i=1;i<=N;++i)
    scanf("%s",map[i]);
for(i=0;i<M;i++)
     map[0][i]='H';
    map[0][i]=0;
}
int getNum(int s)
{
int k=s;
if(stateNum[s] == -1)
{
   int n=0;
   while (k)
   {
    n++;
    k=k&(k-1);
   }
   stateNum[s]=n;
}
return stateNum[s];
}
int IsValidateRows(int s,int row)
{
int k=s;
if((int)staterow[s][row] == -1)
{
   int j = M ;
   while(k)
   {
    int num = k % 2;
    k /= 2;
    -- j;
    if ( num && map[row][j]=='H' )
    {
     staterow[s][row]=0;
     return 0;
    }
   }
   staterow[s][row]=1;
}
return staterow[s][row];
}
int IsValidateStates(int state1,int state2)
{
int s1=state1,s2=state2;
if((int)statestate[s1][s2] == -1)
{
   int num1,num2;
   while (state1 && state2)
   {
    num1 = state1 % 2;
    num2 = state2 % 2;
    if( num1== 1 && num2 ==1)
    {
     statestate[s1][s2]=0;
     break;
    }
    state1 /= 2;
    state2 /= 2;
   }
   if(statestate[s1][s2]==-1)
      statestate[s1][s2]=1;
}
return statestate[s1][s2];
}