poj1185

/* solution: 状压dp d[i][j][k]表示第i行的炮兵拜访情况为i,地i-1行炮兵拜访情况为k的前i行所能放的炮兵的最大解 初始化d[0][j][0] = soldier_num[j]; d[1][i][j] = max(d[1][i][j], d[0][j][0] + soldier_num[i]) note: 注意d[i][j][k]中的j表示编号为j的情况，因为如果直接存二进制状态的话，会由于数目太多导致 效率缓慢。所以与soldier_num,state两个数组建立了映射关系。soldier_num[i]表示编号为i 的状态有多少个士兵。state[i]表示编号为i的情况的状态（即二进制数）。 date: 2016.8.16 */ #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int maxm = 10 + 5; const int maxn = 100 + 10; char g[maxn][maxm]; int m, n, dex; int state[70]; //表示每一行的可能的所有状态 int soldier_num[70]; //soldier_num[i]表示编号为i的状态有多少个士兵 int hill[maxn]; //hill[i]表示第i行的山地情况 int d[maxn][70][70]; //d[i][j][k]表示第i行的炮兵拜访情况为i,地i-1行炮兵拜访情况为k的前i行所能放的炮兵的最大解 #define conflict(a, b) a&b int main() { //freopen("input.txt", "r", stdin); memset(state, 0, sizeof(state)); memset(soldier_num, 0, sizeof(soldier_num)); memset(d, 0, sizeof(d)); memset(hill, 0, sizeof(hill)); //初始化 scanf("%d%d", &n, &m); for(int i = 0; i < n; i++) { scanf("%s", g[i]); for(int j = 0; j < m; j++) if(g[i][j] == 'H') hill[i] += (1 << j); } //读入数据的同时处理山地的分布情况 //对于每种可能的状态，求解出对应的炮兵数量 dex = 0; for(int i = 0; i < (1 << m); i++) { if(conflict(i, i << 1) || conflict(i, i << 2)) continue; int tmp = i; while(tmp) { soldier_num[dex] += tmp & 1; tmp = tmp >> 1; } state[dex++] = i; } //初始化d[0][j][0] = soldier_num[j]; d[1][i][j] = max(d[1][i][j], d[0][j][0] + soldier_num[i]) for(int i = 0; i < dex; i++) { //初始化0行 if(conflict(hill[0], state[i])) continue; //山地不能摆放炮兵 d[0][i][0] = soldier_num[i]; } for(int i = 0; i < dex; i++) { //初始化1行 if(conflict(hill[1], state[i])) continue; for(int j = 0; j < dex; j++) { if(conflict(hill[0], state[j])) continue; if(conflict(state[i], state[j])) continue; d[1][i][j] = max(d[1][i][j], d[0][j][0] + soldier_num[i]); } } //dp for(int r = 2; r < n; r++) { for(int i = 0; i < dex; i++) { if(conflict(state[i], hill[r])) continue; for(int j = 0; j < dex; j++) { if(conflict(state[j], hill[r-1])) continue; if(conflict(state[j], state[i])) continue; for(int k = 0; k < dex; k++) { if(conflict(state[k], hill[r-2])) continue; if(conflict(state[k], state[i])) continue; if(conflict(state[k], state[j])) continue; d[r][i][j] = max(d[r][i][j], d[r-1][j][k] + soldier_num[i]); } } } } //print ans int ans = 0; for(int i = 0; i < dex; i++) { for(int j = 0; j < dex; j++) { //if(conflict(state[i], state[j])) continue; ans = max(ans, d[n-1][i][j]); } } printf("%d\n", ans); return 0; }