hdu4539(状态压缩)

题目链接：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）这些位置都不能有其他的士兵。

思路：状态压缩，相邻三行产生关系可以通过添加状态的维数来解

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
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<<m);
        for(i = 0; i < n; i ++)
        for(j = 0; j < m; j ++)
        scanf("%d",&map[i][j]);
        int ans = 0;
        memset(d, 0, sizeof(d));
        for(i = 0; i < n; i ++)//第i行
        {
            for(j = 0; j < M; j ++)//枚举第i行的状态
            {
                for(k = 0; k < M; k ++)//第i-1行状态
                {
                    if((sta[j]&(sta[k]>>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\n",ans);
    }
    return 0;
}

hdu4539(状态压缩),布布扣,bubuko.com

hdu4539(状态压缩)

原文：http://blog.csdn.net/jzmzy/article/details/20950205