C小加

厚德 博学 求真 至善 The bright moon and breeze
posts - 145, comments - 195, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

poj 1185 炮兵阵地 (状态压缩DP)

Posted on 2012-03-20 21:11 C小加 阅读(1788) 评论(1)  编辑 收藏 引用 所属分类: 解题报告

弱爆了。我调试了一个下午加半个晚上,最后重写了一遍AC了。2xx ms的时间,在自己oj上排倒数第一。

 

我的第二道状态压缩DP,也是周伟论文《状态压缩》里的一道例题,核心思想这篇论文分析的很清楚,建议学习状态压缩的同学一定要看一下。

 

这道题做的很过瘾,收获很多,各种二进制的解法。还有状就是态数的求法也很强,刚开始写的时候还准备DFS呢,后来大牛告诉我直接枚举所有状态进行删除就可以了,好吧,删除的判断又是二进制。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXM=63;
int e[103];
int m,n;
int s[MAXM];
int c[MAXM];
int f[103][MAXM][MAXM];
int cnt;
//输入数据
void input()
{
    memset(e,0,sizeof(e));
    char str[13];

    for(int i=0;i<m;i++)
    {
        scanf("%s",str);
        for(int j=0;j<n;j++)
        {
            if(str[j]=='H') e[i]=(e[i]<<1)|1;
            else e[i]=e[i]<<1;
        }
    }
}
//比较左右间隔是否为2
bool fit(int x)
{
    if( x & (x<<1) ) return false;
    if( x & (x<<2) ) return false;
    return true;
}
//二进制中1的个数
int num1(int x)
{
    int count=0;
    while(x>0)
    {
        count++;
        x= x & (x-1);
    }
    return count;
}
//寻找状态数
void DFS()
{
    int total=1<<n;
    for(int i=0;i<total;i++)
    {
        if(fit(i))
        {
            s[++cnt]=i;
            c[cnt]=num1(i);
        }
    }
}
//DP
void DP()
{
    //初始化
    memset(f,-1,sizeof(f));
    for(int i=0;i<=cnt;++i)
    {
        if(s[i]&e[0])continue;
        f[0][i][0]=c[i];
    }

    for(int i=1;i<m;++i)
    {
        for(int j=0;j<=cnt;++j)
        {
            if(s[j]&e[i])continue;
            for(int k=0;k<=cnt;++k)
            {
                if(s[j]&s[k])continue;
                for(int l=0;l<=cnt;++l)
                {
                    if(s[j]&s[l]) continue;
                    if(f[i-1][k][l]==-1) continue;
                    f[i][j][k]=max(f[i][j][k],f[i-1][k][l]+c[j]);
                }
            }
        }
    }
}
//输出
void print()
{
    int ans=0;
    if(m!=0)
    for(int i=0;i<=cnt;i++)
        for(int j=0;j<=cnt;j++)
            ans=max(ans,f[m-1][i][j]);
    printf("%d\n",ans);
}

int main()
{
    //freopen("in.txt","r",stdin);

    while(scanf("%d %d",&m,&n)!=EOF)
    {
        cnt=-1;
        input();
        DFS();
        DP();
        print();

    }

    return 0;
}

Feedback

# re: poj 1185 炮兵阵地 (状态压缩DP)[未登录]  回复  更多评论   

2013-08-17 21:15 by ACE
能否详细点啊!我不会运用位运算,

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理