题目链接：?id=1185题目大意：中文题，如题题目分析：经典的状压dp，现在才做，因为列数很小，因此我们可以把行状态用二进制压缩，1表示该点放炮兵，0表示不放，因为H位置不能放，所以考虑，先把每行的地形状态压缩存在f数组中，其次分析每行的可行状态，一位一个炮兵可以攻击到其左边右边两格位置，所以显然，同一行，不能出现连续两个1，即0011，也不能相隔一个位置出现1，即0101，这都是非法的，只有至少相隔两点为1才合法，比如1001，对于每行我们还要记录的是状态对应的1的个数，即放了多少炮兵，然后我们再来看列，与行类似，任意连续三行的同一列，只能有一个1，因为一个炮兵的纵向攻击范围也是两格，即其纵向状态只与前两行有关，因此我们记dp[i][j][k]为第i行状态为j，第i－1行状态为k时能放的最多炮兵数量，则dp[i][j][k] = dp[i – 1][k][l] + stnum[i]，，(i >= 2)l表示的是第i－2行的状态，stnum[i]表示的是第i行放的炮兵数量，对于第一第二行我们单独处理，从第三行开始，直接进行dp，最后dp[n-1][i][j]的最大值即为答案#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int const MAX = 105;int sta[MAX], stnum[MAX], f[MAX];int dp[MAX][MAX][MAX];char s[MAX][15];int main(){int n, m, cnt = 0;scanf("%d %d", &n, &m);for(int i = 0; i < n; i++)scanf("%s", s[i]);memset(f, 0, sizeof(f));for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)if(s[i][j] == 'H')f[i] += (1 << j);for(int j = 0; j < (1 << m); j++){int tmp = j;if((j & (j << 1)) || (j & (j << 2)))continue;while(tmp){stnum[cnt] += (tmp & 1);tmp >>= 1;}sta[cnt ++] = j;}for(int i = 0; i < cnt; i++){if(f[0] & sta[i])continue;dp[0][i][0] = stnum[i];}for(int i = 0; i < cnt; i++){if(f[1] & sta[i])continue;for(int j = 0; j < cnt; j++){if(f[0] & sta[j])continue;if(sta[i] & sta[j])continue;dp[1][i][j] = max(dp[1][i][j], dp[0][j][0] + stnum[i]);}}for(int r = 2; r < n; r++){for(int i = 0; i < cnt; i++){if(f[r] & sta[i])continue;for(int j = 0; j < cnt; j++){if(f[r – 1] & sta[j])continue;if(sta[i] & sta[j])continue;for(int k = 0; k < cnt; k++){if(f[r – 2] & sta[k])continue;if((sta[i] & sta[k]) || (sta[j] & sta[k]))continue;dp[r][i][j] = max(dp[r][i][j], dp[r – 1][j][k] + stnum[i]);}}}}int ans = 0;for(int i = 0; i < cnt; i++)for(int j = 0; j < cnt; j++)ans = max(ans, dp[n – 1][i][j]);if(n == 0 || m == 0)printf("0\n");elseprintf("%d\n", ans);}
坚守自己的原则，世界上的诱-惑很多，
