状态压缩 – POJ 1185 炮兵阵地【状态压缩DP】

核心算法：

dp状态压缩

中文题

分析：

graph[i]存储第i行的地形，用一二进制数表示:

  1. 山地对应位置为1
  2. 平地对应位置为0

leg[N]中存放所有能够合法的单行安排状态，用二进制数表示：

  1. 驻兵对应位置为1
  2. 不驻兵对应位置为0

dp[i][j][k]表示第i行状态为j，i-1行状态为k时最多的哨兵数目，j,k均对应leg[]中状态

dp[i][cur][p1] = getmax(dp[i][cur][p1],dp[i-1][p1][p2]+leg[cur].army);

其中：

  1. p1为第i-1层的合法行存放状态
  2. p2为第i-2层的合法行存放状态，
  3. cur为当前即第i层合法行存放状态
  4. p1,p2,cur满足互不冲突，即三行数据中的任何一列驻兵数最多只出现一个
    cur满足不在山地驻兵，即满足leg[cur].status&graph[i]==0

由此，最多的驻兵数即为dp[n-1][][]中的最大值

PS:用了两个小时写代码，结果因为一个数组开小了，纠结了近四个小时。。。真悲剧。。。

Answer


#include<stdio.h>
#include<string.h>
constint N =1<<11;
constint LEG_NUM =90;
int dp[101][LEG_NUM][LEG_NUM];//
int graph[110];

struct node
{
 int army;//部队个数
int status;//布局
}leg[LEG_NUM];//存储单行合法的炮兵布局
int legNum;

void getLeg()//获取合法单行
{
    int i;
 legNum =0;
 leg[legNum].army =0;
 leg[legNum++].status =0;

 for(i=1;i<N;i++)
 {
  int temp =i;
  if(((temp<<1)&temp)||((temp<<2)&temp))continue;

  leg[legNum].status=i;
  leg[legNum].army =0;
  temp = i;
  while(temp)
  {
   if(temp&1)leg[legNum].army++;
   temp>>=1;
  }
  legNum++;
 }
}

inline int getmax(int a,int b)
{
 return a>b?a:b;
}

int getId(int x)//或许当前状态的上限
{
 int left =0;
 int right = legNum;
 int ans =0;
 while(left<=right)
 {
  int mid = (left+right)>>1;
  if(leg[mid].status>x)
  {
   ans =mid;
   right=mid-1;
  }
  else
   left=mid+1;
 }

 return ans;
}

void outputAns(int n,int legnum)//计算并输出答案
{
  int ans =0;
   for(int i=0;i<legnum;i++)
    for(int j=0;j<legnum;j++)
     ans = getmax(dp[n-1][i][j],ans);

   printf("%d\n",ans);
}

int main()
{
 getLeg();
 int n,m;
 while(scanf("%d%d",&n,&m)!=EOF)
    {
         char str[15];
   int i,j;
   for(i=0;i<n;i++)
   {
    scanf("%s",str);
    graph[i]=0;
    for(j=0;j<m;j++)
    {
     if(str[j]=='P')
      graph[i]=graph[i]*2+0;//平原为0
else
      if(str[j]=='H')
      graph[i]=graph[i]*2+1;//山地为1
    }
   }
   
   int legnum = getId((1<<m)-1);
 
   for(i=0;i<n;i++)
    for(j=0;j<legnum;j++)
     for(int k=0;k<legnum;k++)
      dp[i][j][k]=0;
   if(n==0)
   {
    printf("0\n");
    continue;
   }
   
   //初始化第一行信息
for(i=0;i<legnum;i++)
   {
    if((leg[i].status&graph[0])==0)//排除在山地安排
      dp[0][i][0] = leg[i].army;
   }

    if(n==1)
   {
    outputAns(n,legnum);
    continue;
   }

   //初始化第二行信息

   for(i=0;i<legnum;i++)
   {
    if((leg[i].status&graph[1])==0)//排除在山地安排
for(j=0;j<legnum;j++)
    {
     if((leg[i].status&leg[j].status)==0)//两行没有冲突
     {
      dp[1][i][j] = getmax(dp[1][i][j],dp[0][j][0]+leg[i].army);
     }
    }
   }

   for(i=2;i<n;i++)
   {
    for(int cur =0;cur<legnum;cur++)
    {
     if((leg[cur].status&graph[i])==0)//排除在山地驻军
     {
      for(int p1=0;p1<legnum;p1++)
      {
       if((leg[p1].status&leg[cur].status)==0)//与上层没有冲突
       {
        for(int p2=0;p2<legnum;p2++)
        {
         if((leg[p2].status&leg[cur].status)==0)
          //与上上层没有冲突
         {
          dp[i][cur][p1] = getmax(dp[i][cur][p1],dp[i-1][p1][p2]+leg[cur].army);
         }
        }
       }
      }
     }
    }
   }


   outputAns(n,legnum);
   
 }
 return0;
}