首页 > ACM题库 > HDU-杭电 > HDU 4539-郑厂长系列故事――排兵布阵-动态规划-[解题报告]HOJ
2015
02-17

HDU 4539-郑厂长系列故事――排兵布阵-动态规划-[解题报告]HOJ

郑厂长系列故事――排兵布阵

问题描述 :

  郑厂长不是正厂长
  也不是副厂长
  他根本就不是厂长
  事实上
  他是带兵打仗的团长

  一天,郑厂长带着他的军队来到了一个n*m的平原准备布阵。
  根据以往的战斗经验,每个士兵可以攻击到并且只能攻击到与之曼哈顿距离为2的位置以及士兵本身所在的位置。当然,一个士兵不能站在另外一个士兵所能攻击到的位置,同时因为地形的原因平原上也不是每一个位置都可以安排士兵。
  现在,已知n,m 以及平原阵地的具体地形,请你帮助郑厂长计算该阵地,最多能安排多少个士兵。

输入:

输入包含多组测试数据;
每组数据的第一行包含2个整数n和m (n <= 100, m <= 10 ),之间用空格隔开;
接下来的n行,每行m个数,表示n*m的矩形阵地,其中1表示该位置可以安排士兵,0表示该地形不允许安排士兵。

输出:

输入包含多组测试数据;
每组数据的第一行包含2个整数n和m (n <= 100, m <= 10 ),之间用空格隔开;
接下来的n行,每行m个数,表示n*m的矩形阵地,其中1表示该位置可以安排士兵,0表示该地形不允许安排士兵。

样例输入:

6 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

样例输出:

2

这题和poj1185http://poj.org/problem?id=1185很像…

首先枚举了一下,对于一行来说有效状态最多169,那么可以DP[i][j][k],第i–1行状态为j第i行状态为k的ans。然后可以枚举j,k,l,DP[i][j][k]=max{DP[i+1][k][l]}+count[k],时间是100*169^3,但是由于部分位置不能摆放士兵使得实际时间远远小于上面那个上界。我预处理了一下,把连续3行的可能情况保存起来,最多有62001种情况,那么DP的上界就是100*62001,预处理的上界是169^3。

这题还有别的解法...最大独立点集...还有一种100*2^10的状压dp …(现在都不会写,先Mark一下…)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<fstream>
using namespace std;
int Map[105],Sta[15][200],Num[15][200];
int Rel[15][160000][3];
int Cnt1[15],Cnt2[15];
int DP[105][200][200];
void PPSta(int m)
{
    int i,j,bound,tmp;
    bound=(1<<m);
    tmp=bound-1;
    Cnt1[m]=0;
    for(i=0;i<bound;++i)
    {
        if((((i<<2)&tmp)&i)==0&&((i>>2)&i)==0)
        {
            Sta[m][Cnt1[m]]=i;
            for(j=0;j<m;++j)
                if((1<<j)&i)
                    Num[m][Cnt1[m]]++;
            Cnt1[m]++;
        }
    }
}
void PSta()
{
    int i;
    memset(Num,0,sizeof(Num));
    for(i=1;i<=10;++i)
        PPSta(i);
}
void PPRel(int m)
{
    Cnt2[m]=0;
    int i,j,k,o,p,q,bound=Cnt1[m],tmp=(1<<m)-1;
    for(i=0;i<bound;++i)
    {
        o=Sta[m][i];
        for(j=0;j<bound;++j)
        {
            p=Sta[m][j];
            if((((o<<1)&tmp)&p)==0&&((o>>1)&p)==0)
            {
                for(k=0;k<bound;++k)
                {
                    q=Sta[m][k];
                    if((((p<<1)&tmp)&q)==0&&((p>>1)&q)==0&&((q&o)==0))
                    {
                        Rel[m][Cnt2[m]][0]=i;
                        Rel[m][Cnt2[m]][1]=j;
                        Rel[m][Cnt2[m]][2]=k;
                        Cnt2[m]++;
                    }
                }
            }
        }
    }
//    cout<<Cnt2[m]<<endl;
}
void PRel()
{
    int i;
    for(i=1;i<=10;++i)
        PPRel(i);
}
//***************************************************************************
int main()
{
    PSta(),PRel();
    int n,m,i,j,k,o,p,q,a,b,c,tmp,bound,ans;
//    ifstream fin("data.txt");
//    while(fin>>n>>m)
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        tmp=(1<<m)-1;
        memset(Map,0,sizeof(Map));
        memset(DP,0,sizeof(DP));
        for(i=1;i<=n;++i)
        {
            for(j=1;j<=m;++j)
            {
//                fin>>k;
                scanf("%d",&k);
                k^=1;
                Map[i]=Map[i]*2+k;
            }
        }
//        for(i=1;i<=n;++i)
//            cout<<Map[i]<<endl;
        bound=Cnt2[m];
        for(i=0;i<Cnt1[m];++i)
        {
            o=Sta[m][i];
            if((o&Map[n-1])==0)
            {
                for(j=0;j<Cnt1[m];++j)
                {
                    q=Sta[m][j];
                    if((q&Map[n])==0&&((((o<<1)&tmp)&q)==0&&((o>>1)&q)==0))
                    {
                        DP[n][i][j]=Num[m][j];
//                        cout<<n<<" "<<DP[n][i][j]<<endl;
                    }
                }
            }
        }
//        cout<<Rel[m][0][0]<<" "<<Rel[m][0][1]<<" "<<Rel[m][0][2]<<endl;
        for(i=n-1;i>0;--i)
        {
            for(j=0;j<bound;++j)
            {   
                a=Rel[m][j][0],b=Rel[m][j][1],c=Rel[m][j][2];
                o=Sta[m][a],p=Sta[m][b],q=Sta[m][c];
                if((o&Map[i-1])==0&&((p&Map[i])==0)&&((q&Map[i+1])==0))
                {
//                    cout<<i<<" "<<Num[m][b]<<endl;
                    DP[i][a][b]=max(DP[i][a][b],DP[i+1][b][c]+Num[m][b]);
                }
            }
        }
        ans=0;
        for(i=0;i<bound;++i)
            ans=max(ans,DP[1][0][i]);
        printf("%d\n",ans);
    }
//    getchar();
    return 0;
}     

 

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/byijie/article/details/8742492