fengyunfly吧 关注:9贴子:102
  • 0回复贴,共1
  • 202.101.104.*
/*
WC2007_SC_HS
《炮兵阵营》——经典的状态压缩动态规划问题
*/
#include <stdio.h>
#include <stdlib.h>
#define maxn 300
int num[maxn],size;
int map[maxn];
int score[maxn];
int f[2][maxn][maxn];
int n,m;
inline void setbit(int &a,int b){
  a|=(1<<(b-1));
}
inline int getbit(int a,int b){
  return ((a&(1<<(b-1)))>0);
}
void dfs(int step,int state,int now){//Searching procedure for calculating the states that in a line
  if (step>m){
    num[++size]=state;
    score[size]=now;
    return;
  }
  int np=state;
  dfs(step+1,state,now);
  if (!((step>1 && getbit(state,step-1)) || (step>2 && getbit(state,step-2)))){
    setbit(np,step);
    dfs(step+1,np,now+1);
  }
}
inline int fight(int a,int b){
  return a&b;
}
void fill(){//Dynamic procedure
  int row,i,j,k,now,last,max,res=0,tmp;
  last=0;
  now=1;
  for (i=1;i<=size;i++){
    if (fight(num[i],map[1])) continue;
    for (j=1;j<=size;j++){
      if (fight(num[j],map[2])) continue;
      if (fight(num[i],num[j])) continue;
      f[last][i][j]=score[i]+score[j];
    }
  }
  for (row=3;row<=n;row++){
    for (i=1;i<=size;i++){
      if (fight(map[row],num[i])) continue;
      for (j=1;j<=size;j++){
        if (fight(map[row-1],num[j])) continue;
        if (fight(num[i],num[j])) continue;
        max=0;
        for (k=1;k<=size;k++){
          if (fight(map[row-2],num[k])) continue;
          if (fight(num[k],num[i])) continue;
          if (fight(num[k],num[j])) continue;
          tmp=f[last][k][j]+score[i];
          if (tmp>max) max=tmp;
        }
        f[now][j][i]=max;
      }
    }
    last=now;
    now=1-now;
  }
  for (i=1;i<=size;i++){
    if (fight(map[n-1],num[i])) continue;
    for (j=1;j<=size;j++){
      if (fight(map[n],num[j])) continue;
      if (fight(num[i],num[j])) continue;
      if (f[last][i][j]>res) res=f[last][i][j];
    }
  }
  printf("%d\n",res);
}
int onlyone(){//deal the situation N=1
  if (n>1) return 0;
  int i,max=0;
  for (i=1;i<=size;i++){
    if (fight(num[i],map[1])) continue;
    if (score[i]>max) max=score[i];
  }
  printf("%d\n",max);
  return 1;
}
int main(){
  int i,j,row;
  char tmp;
  freopen("cannon.in","r",stdin);
  freopen("cannon.out","w",stdout);
  while (scanf("%d%d\n",&n,&m)!=EOF){
    size=0;
    for (i=1;i<=n;i++){
      row=0;
      for (j=1;j<=m;j++){
        scanf("%c",&tmp);
        if (tmp=='H') setbit(row,j);
      }
      map[i]=row;
      scanf("\n");
    }
    dfs(1,0,0);
    if (onlyone()) exit(0);
    fill();
  }
  return 0;
}



1楼2008-06-25 18:37回复