POJ 1185 炮兵阵地 （状态压缩dp）

原来写过这篇博哦，超详细诶。。。哈哈！！http://blog.csdn.net/u011262722/article/details/9266571

再写一遍，觉得比较重要和值得注意的两点是：

1】递推时i行、i-1行 、i-2行选择状态的三个for循环的嵌套顺序。

感觉顺序好像没什么。我不知道为什么第一次写的是时候是最外层是i，然后是i-2行，最内层是i-1行。

其实由于第i行的状态是由前两行得到，而i-1行是由i-2得到。所以由外到内应该是i、i-1、i-2比较好理解吧。。。

我也试过了，是可行的。

2】保存所有满足硬性条件的状态数组到底要开多大。（在1<<10范围内选择的满足不存在相邻两个1且不存在

间隔一个有1的状态数）

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

int cur[105],dp[105][70][70],ok[70],num[110],cnt;
char mp[105][15];

int max(int x,int y)
{
    return x>y?x:y;
}

bool isok(int t)
{
    if(t&(t<<1))
        return false;
    if(t&(t<<2))
        return false;
    return true;
}

void init(int n)
{
    cnt=1;
    int tot=(1<<n);
    for(int i=0;i<tot;i++)
    {
        if(isok(i))
            ok[cnt++]=i;
    }
}

int count_1(int x)
{
    int sum=0;
    while(x)
    {
        if(x&1)
            sum++;
        x>>=1;
    }
    return sum;
}

int main()
{
    int m,n,ans;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        if(n==0 && m==0) break;
        memset(dp,-1,sizeof(dp));
        memset(cur,0,sizeof(cur));
        init(n);
        for(int i=1;i<=m;i++)
        {
            scanf("%s",mp[i]+1);
            for(int j=1;j<=n;j++)
            {
                if(mp[i][j]==‘H‘)
                    cur[i]+=(1<<(j-1));
            }
        }
        for(int i=1;i<cnt;i++)
        {
            num[i]=count_1(ok[i]);
            if((ok[i]&cur[1])==0)
                dp[1][1][i]=num[i];
        }
        for(int i=2;i<=m;i++)
        {
            for(int j=1;j<cnt;j++)
            {
                if(ok[j]&cur[i])
                    continue;
                for(int k=1;k<cnt;k++)
                {
                    if(ok[k]&ok[j])
                        continue;
                    for(int t=1;t<cnt;t++)
                    {
                        if(ok[t]&ok[j])
                            continue;
                        if(dp[i-1][k][t]==-1)
                            continue;
                        dp[i][t][j]=max(dp[i][t][j],dp[i-1][k][t]+num[j]);
                    }
                }
            }
        }
        ans=0;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<cnt;j++)
            {
                for(int k=1;k<cnt;k++)
                {
                    if(ans<dp[i][j][k])
                        ans=dp[i][j][k];
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

POJ 1185 炮兵阵地 （状态压缩dp）

原文：http://blog.csdn.net/u012841845/article/details/18707529