poj 1185 상압 DP

만약 이전 블로그의 문제를 풀었다면, 이 문제는 dp방정식과 함수를 쉽게 내놓을 수 있을 것이다
dp[i][j][k]는 현재 i행, i행 상태는 k, i-1행 상태가 j일 때의 포병 총수
1. dp[][][]를 0이 아닌 -1로 초기화합니다. 그러면 이전에 있었던 상태를 표시할 수 있습니다. 계속 미루지 마십시오. 그렇지 않으면 오해가 있을 수 있습니다.
2. 초기화, dp[1][0][i]0은 첫 번째 합법적인 상태가 전체 0의 상태임을 나타낸다
처음에 샘플을 봤는데 그 구이진 안에 1이 몇 개 있어서 틀렸어요. 아이고...

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <cmath>
#include <map>
#include <queue>
using namespace std;

#define ls(rt) rt*2
#define rs(rt) rt*2+1
#define ll long long
#define rep(i,s,e) for(int i=s;i<e;i++)
#define repe(i,s,e) for(int i=s;i<=e;i++)
#define IN(s) freopen(s,"r",stdin)
#define CL(a,b) memset(a,b,sizeof(a))

const int MAXN = 13*13;

ll dp[MAXN][70][70];
int all[70];
int sta[MAXN*MAXN];//      
char mat[MAXN*MAXN][MAXN];
int bit[1<<12];
int scnt,n,m;
//schar mat[MAXN*MAXN][MAXN];

int cal(int x)
{
    int ret=0;
    while(x)
    {
        if(x&1)ret++;
         x/=2;
    }
    return ret;
}

void init()
{
    CL(bit,0);
    CL(dp,0xff);
    scnt=0;
    int tot=1<<m;
    for(int i=0;i<tot;i++)
    {
        if(i&(i<<1) || i&(i<<2) || i&(i>>1) || i&(i>>2));
        else
        {

            all[scnt]=i;
            bit[scnt]=cal(i);
            ///
            //printf("##%d bit=%d
",i,bit[scnt]);
            //////
            scnt++;
        }
    }
}

int legal(int x, int y) //      
{
    //if(x&y || x&(y<<1) || x&(y<<2) || x&(y>>1) || x&(y>>2))
    if( x&y ) return 0;
    else  return 1;
}

int main()
{
    //IN("poj1185.txt");
    char c;

    while(~scanf("%d%d",&n,&m))
    {
        getchar();
        init();
        sta[0]=0;
        for(int i=1;i<=n;i++)
        {
            sta[i]=0;
            for(int j=1;j<=m;j++)
            {
                mat[i][j]=getchar();
                if(mat[i][j] == 'H')sta[i]+=(1<<(m-j));
            }
            getchar();
        }
        int scnt2=scnt;
        /*int scnt2=0,tmp=1<<m;
        while(all[scnt2]<tmp)///////////
            scnt2++;*/
        //scnt2--;
        for(int i=0;i<scnt2;i++)
            if(legal(sta[1],all[i]))
                dp[1][0][i]=bit[i];
        //////////////////////////
       // rep(i,0,scnt2)
         //   printf("%lld ",dp[1][0][i]);
       // putchar('
');
        ///////////////////////////
        for(int i=2;i<=n;i++)
        {
            for(int j=0;j<scnt2;j++)//i
            {
                if(!legal(sta[i],all[j]))continue;
                for(int k=0;k<scnt2;k++)//i-1
                {
                    if(!legal(sta[i-1],all[k]))continue;
                    if( all[j]&all[k] )continue;    //   
                    for(int p=0;p<scnt2;p++)//i-2
                    {
                        if(!legal(sta[i-2],all[p]))continue;
                        if( all[j]&all[p] || all[k]&all[p] )continue;   //   
                        if(dp[i-1][p][k] == -1)continue;//   
                        dp[i][k][j]=max(dp[i-1][p][k]+bit[j],dp[i][k][j]);
                    }
                }
            }
        }
        ll ans=0;
        for(int i=0;i<scnt2;i++)
            for(int j=0;j<scnt2;j++)
                ans=max(ans,dp[n][j][i]);
        printf("%lld
",ans);
    }
    return 0;
}