POJ-1185 포병 진지 동적 기획 + 상태 압축

점차적으로 추진할 때 세 연속층의 관계에 의존하기 때문이다.처음에 직접적인 삼중for순환을 생각했지만 여기서 문제가 하나 있다. 바로 상층의 0위치에는 상층부는 0과 1 두 가지 가능성을 포함하고 후자는 현재 행에 제약이 있기 때문에 이 방법은 안 된다.물론 상태수를 늘려 상태가 1에서 0으로 옮겨왔는지 나타낼 수 있는 방법이 있다.(이 문제의 해법은 다진법의 상태 압축을 채택한 것이다).인터넷상에서 다른 사람의 문제풀이 보고서를 힐끗 쳐다보았다.순간적으로 3층 사이에 관계가 발생한다는 것을 깨달았다. 그러면 연속된 2층을 직접 기록한다. 비록 공간적으로 다진적인 아름다움에 미치지 못하지만.하지만 이 문제들을 묘사할 수 있다.
코드는 다음과 같습니다.

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
using namespace std;

/*
  :      ,         ,    ,           2   ,  
                       ,           .

  :              ,         ,            , 
               10,               .            
                     .              dp[k][i][j]  
      k     i, i-1    j         .        :
     dp[k][i][j] = sum(dp[k-1][j][k])   k    i     
*/

int N, M, sta[65], idx; //  M=10   ,        65 
int G[105], dp[105][65][65]; //  dp               ,        

void display(int x) {
    for (int i = 0; i < M; ++i) {
        if (x & (1 << i)) {
            printf("1 ");
        } else printf("0 ");
    }
    puts("");
    getchar();
}

void dfs(int pos, int statu, int dist) {
    if (pos == M) {
        sta[++idx] = statu;
    //    display(statu);
        return;
    }
    dfs(pos+1, statu<<1, dist+1);
    if (dist >= 2) {
        dfs(pos+1, statu<<1|1, 0);
    }
}

bool legal(int x, int y) {
    return (x & y) == x; //   x           'P' 
}

bool judge(int x, int y) {
    return !(x & y); //        1
}

int get(int x) {
    int ret = 0;
    for (int i = 0; i < M; ++i) {
        if (x & (1 << i)) {
            ++ret;
        }
    }
    return ret; 
}

int DP() {
    int ret = 0;
    memset(dp, 0, sizeof (dp));
    if (N == 1) { //          ,        
        for (int i = 1; i <= idx; ++i) {
            if (legal(sta[i], G[1])) {
                ret = max(ret, get(sta[i]));    
            }
        }    
        return ret;    
    }
    //      ,     
    for (int i = 1; i <= idx; ++i) { //             
        for (int j = 1; j <= idx; ++j) { //          
            if (legal(sta[i], G[2]) && legal(sta[j], G[1]) && judge(sta[i], sta[j])) {
                dp[2][i][j] = get(sta[i]) + get(sta[j]);
            }
        }
    }
    for (int k = 3; k <= N; ++k) {
        for (int i = 1; i <= idx; ++i) {
            for (int j = 1; j <= idx; ++j) {
                if (!judge(sta[i], sta[j]) || !legal(sta[i], G[k]) || !legal(sta[j], G[k-1])) {
                    continue;
                }
                for (int m = 1; m <= idx; ++m) {
                    if (judge(sta[i], sta[m]) && judge(sta[j], sta[m])) {
                        dp[k][i][j] = max(dp[k][i][j], dp[k-1][j][m]);
                    }
                }
                dp[k][i][j] += get(sta[i]);
            }
        }
    }
    for (int i = 1; i <= idx; ++i) {
        for (int j = 1; j <= idx; ++j) {
            ret = max(ret, dp[N][i][j]);
        }
    }
    return ret;
}

int main() {
    char str[15];
    while (scanf("%d %d", &N, &M) == 2) {
        idx = 0, dfs(0, 0, 2);
    //    printf("idx = %d
", idx);
        memset(G, 0, sizeof (G));
        for (int i = 1; i <= N; ++i) {
            scanf("%s", str);
            for (int j = 0; j < M; ++j) {
                G[i] <<= 1, G[i] |= str[j] == 'P'; //    P          
            }
        }
        printf("%d
", DP());
    }
    return 0;    
}