// poj 1185 炮兵阵地 状压dp// 这题和之前做的棋子的差不多，只是这个比之前的变化了一个条// 件，这个条件让的我们不得不考虑在这个状态之前的状态，即在// 一个状态中记录另外一个状态，说的可能有些绕// 这么说吧： dp[i][S][V]表示第i行状态为S(仍然是二进制的数字// 表现形式，比如5是101，表示第一列和第三列放炮兵)，第i-1行// 的状态为V(同样是二进制的数字表现形式)时所能放置的最大的炮// 兵数量，则状态转移为：// dp[i][S][V] = max (dp[i][S][V],dp[i][V][K]+sum[S]);// sum[S]表示S状态中的炮兵的个数(即其中1的个数)，// 则最后的所有S，和 V 的dp[0][S][V]的max就是我们所求的答案// 这题有很多的细节要处理，比如所有在一行合法的状态预先// 求出来，这样枚举状态的时候就可以直接判断那些本来就合法的// 起到了剪枝的作用，第二个就是边界问题，对于一般的情况// dp[i][S][V] = -1 , 另外我们要把每个合法的状态的初值都要放// 进去，dp[0][(合法的状态)][0]= 合法的炮兵数。// 大牛们的想法真的是大牛啊，膜拜不已// 其实这题我真的不会写，看到了大牛们的解题报告都看了两三// 小时，然后才真正的看懂了，还自己敲一遍wa了无数发，最后才// 真正的ac。继续练吧，这题当作自己的一个宝贵的经验。// 这题，还有很多需要考究的地方，，继续练吧。。。#include <algorithm>#include <bitset>#include <cassert>#include <cctype>#include <cfloat>#include <climits>#include <cmath>#include <complex>#include <cstdio>#include <cstdlib>#include <cstring>#include <ctime>#include <deque>#include <functional>#include <iostream>#include <list>#include <map>#include <numeric>#include <queue>#include <set>#include <stack>#include <vector>#define ceil(a,b) (((a)+(b)-1)/(b))#define endl '\n'#define gcd __gcd#define highBit(x) (1ULL<<(63-__builtin_clzll(x)))#define popCount __builtin_popcountlltypedef long long ll;using namespace std;const int MOD = 1000000007;const long double PI = acos(-1.L);template<class T> inline T lcm(const T& a, const T& b) { return a/gcd(a, b)*b; }template<class T> inline T lowBit(const T& x) { return x&-x; }template<class T> inline T maximize(T& a, const T& b) { return a=a<b?b:a; }template<class T> inline T minimize(T& a, const T& b) { return a=a<b?a:b; }int dp[105][70][70];int state[70];int sum[70];int mp[105];char str[15];bool ok(int x){if (x&(x>>1))return false;if (x&(x>>2))return false;return true;}int get(int x){int i=0;while(x){if (x&1)i++;x>>=1;}return i;}int n,m;int num;void find(){num=0;for (int i=0;i<(1<<m);i++){if (ok(i)){state[num] = i;sum[num] = get(i);num++;}}}void init(){memset(mp,0,sizeof(mp));for (int i=0;i<n;i++){scanf("%s",str);for (int j=0;str[j]!=0;j++)if (str[j]=='H')mp[i] = mp[i] | (1<<j);}}void solve(){find();memset(dp,-1,sizeof(dp));for (int i=0;i<num;i++)if (!(state[i]&mp[0]))dp[0][i][0] = sum[i];for (int i=1;i<n;i++){for (int j=0;j<num;j++){if (mp[i]&state[j])continue;for (int k=0;k<num;k++){if (state[j]&state[k])continue;for (int l=0;l<num;l++){if (state[j]&state[l])continue;if (state[k]&state[l])continue;if (dp[i-1][k][l]==-1)continue;dp[i][j][k] = max(dp[i-1][k][l]+sum[j],dp[i][j][k]);}}}}int ans=0;for (int i=0;i<num;i++){for (int j=0;j<num;j++){//if (state[i]&state[j])continue;ans = max(ans,dp[n-1][i][j]);}}printf("%d\n",ans);}int main() {//find();//freopen("G:\\Code\\1.txt","r",stdin);while(scanf("%d%d",&n,&m)!=EOF){init();solve();}return 0;}
使你疲倦的不是前面的高山，而是你鞋里的一粒沙子。
