상태 압축

제목 링크:hdu4539
맨해튼 거리 - 두 점의 남북 방향에서의 거리에 동서방향에서의 거리, 즉 d(i, j)=|xi-xj|+|yi-yj|.
이 문제는 각 병사의 맨해튼 거리가 2인 위치에 다른 병사가 있을 수 없다는 것이다. 병사의 위치(i, j)를 가정하면 (i-2, j)(i+2, j)(i, j+2)(i, j+2)(i-1, j-1)(i-1, j+1)(i+1, j-1)(i+1, j-1)(i+1, j+1) 이런 위치에 다른 병사가 있을 수 없다.
사고방식: 상태가 압축되고 세 줄에 인접하여 관계가 생기면 상태의 차원을 추가하여 풀 수 있다.

#include 
#include 
#include 
#include 
using namespace std;
int sta[200];
int map[200][15];
int d[105][200][200];//d[i][j][k]   i  j   ， i-1  k          
int n,m;
int Init(int n)//     
{
    int M = 0;
    for(int i = 0; i < n; i ++)
        if( (i&(i>>2)) == 0 && (i&(i<<2)) == 0 )
             sta[M++] = i;
    return M;
}
int Getsum(int i, int x)
{
    int sum = 0, j = m - 1;
    while(x)
    {
        if(x&1) sum += map[i][j];
        x >>= 1;
        j --;
    }
    return sum;
}
int main()
{
    int i,j,k;
    while(~scanf("%d%d",&n,&m))
    {
        int M = Init(1<>1)) || (sta[j]&(sta[k]<<1))) continue;// i   i-1   
                    if(i == 0)
                    {
                        d[i][j][k] = Getsum(i, sta[j]);
                        ans = max(ans, d[i][j][k]);
                        continue;
                    }
                    int tmp = 0;
                    for(int p = 0; p < M; p ++)// i-2   
                    {
                        if((sta[p]&(sta[k]>>1)) || (sta[p]&(sta[k]<<1))) continue;// i-1   i-2   
                        if(sta[j]&sta[p]) continue;// i   i-2   

                        tmp = max(tmp, d[i-1][k][p]);
                    }
                    d[i][j][k] = tmp + Getsum(i, sta[j]);
                    ans = max(ans, d[i][j][k]);
                }
            }
        }
        printf("%d
",ans);
    }
    return 0;
}