POJ1185 炮兵阵地

  1 #include <iostream>
  2 #include <vector>
  3 #include <string>
  4 #include <map>
  5 using namespace std;
  6 int m,n;
  7 vector<int> warMap;
  8 
  9 map<int,int> LineStatus;
 10 int EndData;
 11 struct KeyVal
 12 {
 13     int key;
 14     int val;
 15 public:
 16     KeyVal(int k,int v):key(k),val(v)
 17     {
 18 
 19     }
 20 };
 21 struct KeyVec
 22 {
 23     int key;
 24     vector<KeyVal> val;
 25 public:
 26     KeyVec(int k):key(k)
 27     {
 28 
 29     }
 30     KeyVec(int k,vector<KeyVal>& v):key(k),val(v)
 31     {
 32 
 33     }
 34 };
 35 typedef vector<KeyVec> PreStatus;
 36 typedef vector<KeyVal> ST;
 37 int GetNum(int val)
 38 {
 39     int result=0;
 40     for (int i=0;i<m;++i)
 41     {
 42         result+=(val>>i)&1;
 43     }
 44     return result;
 45 }
 46 
 47 bool check(int val)
 48 {
 49     if ((val&(val>>2))||(val&(val>>1)))
 50     {
 51         return false;
 52     }
 53     else
 54     {
 55         return true;
 56     }
 57 }
 58 void GetLine(int val,int step,map<int,int>& result)
 59 {
 60     if (step>=m)
 61     {
 62         result.insert(make_pair(val,GetNum(val)));
 63     }
 64     else
 65     {
 66         int tmp=val|(1<<step);
 67         if (check(tmp))
 68         {
 69             GetLine(tmp,step+1,result);
 70         }
 71         GetLine(val,step+1,result);
 72     }
 73 }
 74 void GetUsefulStatus(int i,ST& UsefulStatus)
 75 {
 76     for (map<int,int>::iterator iter=LineStatus.begin();iter!=LineStatus.end();++iter)
 77     {
 78         if (!((iter->first)&warMap[i]))
 79         {
 80             UsefulStatus.push_back(KeyVal(iter->first,iter->second));
 81         }
 82     }
 83 }
 84 
 85 void DP(int step,PreStatus& p)
 86 {
 87     if (step>=n)
 88     {
 89         for (PreStatus::iterator iter=p.begin();iter!=p.end();++iter)
 90         {
 91             for (ST::iterator it2=iter->val.begin();it2!=iter->val.end();++it2)
 92             {
 93                 if (it2->val>EndData)
 94                 {
 95                     EndData=it2->val;
 96                 }
 97             }
 98         }
 99     }
100     else
101     {
102         ST ussta;
103         GetUsefulStatus(step,ussta);
104         PreStatus p2;
105         p2.reserve(60);
106         for (ST::iterator iter=ussta.begin();iter!=ussta.end();++iter)
107         {
108             ST pre;
109             pre.reserve(60);
110             for (PreStatus::iterator itP1=p.begin();itP1!=p.end();++itP1)
111             {
112                 if (iter->key&itP1->key)
113                 {
114                     continue;
115                 }
116                 int num=0;
117 
118                 for (ST::iterator itP2=itP1->val.begin();itP2!=itP1->val.end();++itP2)
119                 {
120                     if ((!(iter->key&itP2->key))&&(itP2->val>num))
121                     {
122                         num=itP2->val;
123                     }
124                 }
125                 pre.push_back(KeyVal(itP1->key,iter->val+num));
126             }
127             if (pre.size()>0)
128             {
129                 p2.push_back(KeyVec(iter->key,pre));
130             }
131         }
132         DP(step+1,p2);
133     }
134 }
135 int main()
136 {
137     cin>>n>>m;
138     for (int i=0;i<n;++i)
139     {
140         string tmp;
141         cin>>tmp;
142         int res=0;
143         for (int j=0;j<tmp.size();++j)
144         {
145             if (tmp[j]-'H'==0)
146             {
147                 res=res|(1<<j);
148             }
149         }
150         warMap.push_back(res);
151     }
152     GetLine(0,0,LineStatus);
153     PreStatus pre;
154     KeyVal ppre(0,0);
155     KeyVec kv(0);
156     kv.val.push_back(ppre);
157     pre.push_back(kv);
158     DP(0,pre);
159     cout<<EndData<<endl;
160 }