poj 1185 포병 진지(상압 DP)

이전 문제와 약간 유사하다.그러나 현재 i행의 상태는 i-1행의 상태와 관련이 있을 뿐만 아니라 i-2행의 상태와도 관련이 있다.앞의 두 줄의 상태를 매거하여 상태 이동을 진행한다. dp[i][s][s1]를 설정하면 i줄의 상태가 s이고 i-1줄의 상태가 s1일 때 가장 많은 포병을 배치할 수 있는 수량을 나타낸다.각각 i-1과 i-2 줄의 상태 s1, s2를 열거하면 다음과 같다.
dp[i][s][s1]=max(dp[i][s][s1],dp[i−1][s1][s2])
이 문제에 대해 줄마다 최대 2^10의 상태가 있는데 분명히 시간과 공간을 직접 매거하는 것은 통하지 않는다.
여러 개의 제한 조건이 존재하기 때문에 사실 많은 상태가 비합법적이라는 것을 알아차렸다.그래서 이런 비합법적인 상태를 미리 선별하여 합법적인 상태를 하나의 수조로 보존할 수 있다.이렇게 매거할 때 합법적인 상태를 직접 매거하면 된다.공간적으로 모든 줄에 대해 합법적인 상태(즉 같은 줄의 포병이 서로 공격하지 않는 상태를 만족시키는 것)는 사실상 60개를 넘지 않기 때문에 상태의 하표로 상태를 표시하는 것을 고려할 수 있어 공간의 복잡도도 최적화되었다.

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define maxn 10
typedef __int64 LL;
char M[100][maxn];
int dp[100][60][60];
int state[60],cur[101],num[60];
bool judge1(int i,int s)
{
    if((cur[i]&s)!=s) return 0;
    return 1;
}

bool judge2(int s1,int s2)
{
    if(s1&s2) return 0;
    return 1;
}

int getnum(int s)
{
    int ans=0;
    while(s) {
        if(s&1) ++ans;
        s>>=1;
    }
    return ans;
}

int main()
{
    int i,j,k,p,n,m,S,cnt;
    while(~scanf("%d%d",&n,&m))
    {
        getchar();
        S=(1<<m);
        cnt=0;
        memset(dp,0,sizeof(dp));
        for(j=0;j<S;++j)
            if((!(j&(j>>1)))&&(!(j&(j>>2)))) {
                    num[cnt]=getnum(j);
                    state[cnt++]=j;
            }
        char c;
        for(i=0;i<n;++i){
            cur[i]=0;
            for(j=0;j<m;++j)
            {
                cin>>c;
                cur[i]=(cur[i]<<1)+(c=='P');
            }
        }


        for(i=0;i<cnt;++i)
            if(judge1(0,state[i])) dp[0][i][0]=num[i];

        for(i=0;i<cnt;++i){
            if(!judge1(1,state[i])) continue;
            for(j=0;j<cnt;++j)
                if(judge1(0,state[j])&&judge2(state[i],state[j])) dp[1][i][j]=max(dp[1][i][j],dp[0][j][0]+num[i]);
        }
        for(i=2;i<n;++i)
            for(j=0;j<cnt;++j)
            {
                if(!judge1(i-2,state[j])) continue;
                for(k=0;k<cnt;++k)
                {
                    if(!judge1(i-1,state[k])) continue;
                    for(p=0;p<cnt;++p)
                        if(judge1(i,state[p])&&judge2(state[p],state[j])&&judge2(state[p],state[k]))
                            dp[i][p][k]=max(dp[i][p][k],dp[i-1][k][j]+num[p]);
                }
            }
        int ans=0;
        for(i=0;i<cnt;++i){
            if(!judge1(n-1,state[i])) continue;
            for(j=0;j<cnt;++j) ans=max(ans,dp[n-1][i][j]);
        }
        printf("%d
",ans);
    }
    return 0;
}