本题的难度给跪了，完全不是自己的能力范围内，看了别人的解题报告才写的
摘自
题目大意：给定一张n*m的地图，地图上有平原p，有山地h，可以在平原p打炮，俗称野战，打炮方向有四个，上下左右，射程是2，要求两个炮不能相互打到，问符合这个要求的情况最多打几个炮?n <= 100,m <= 10.
，类似于递推式dp[i] = dp[i-1] + dp[i-2]的递推过程，而本体每次都是状态间的转移，想到状态转移方程dp[i][j][k] = max(dp[i][k][l]) + sum[j](j和k和l表示当前行状态，前一行状态，，前前行状态,sum[j]表示j状态下在i行放了几个大炮)。
状态数并不是dp[n][1<<m][1<<m] 因为水平方向的炮不能互相冲突，经计算合法的状态数只有60多个即dp[n][70][70]即可
//2140 KB266 msC++2456 B#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int MAXN = 110;int state[MAXN][MAXN] ;//state[i][j]表示第i行第j个合法状态int ans, stnum[MAXN], sum[2222];//stnum[i]表示i行合法的状态数，sum[i]为i状态下1的个数int n, m, map[MAXN][MAXN], dp[MAXN][70][70]; //dp[i][j][k]表示第i行第j个状态第-1行第k个状态含有的最多1的个数void stago(int x){int g=0;for(int i=0;i<m;i++)if(map[x][i]) g+=(1<<i);for(int i=0;i<(1<<m);i++){if((i|g)!=g) continue;if(i&(i>>1)) continue;if(i&(i>>2)) continue;stnum[x]++;state[x][stnum[x]]=i;}}void ini(){memset(stnum,0,sizeof(stnum));stnum[0]=70;}int main(){for(int i=0;i<(1<<10);i++){int s=0;for(int j=0;j<10;j++)if(i&(1<<j)) s++;sum[i]=s;}while(~scanf("%d%d",&n,&m)){ini();char s[20];for(int i=1;i<=n;i++){scanf("%s",s);for(int j=0;s[j];j++)map[i][j]=(s[j]=='P');stago(i);}for(int i=1;i<=stnum[1];i++)for(int j=1;j<=70;j++)dp[1][i][j]=sum[state[1][i]];for(int i=2;i<=n;i++)for(int j=1;j<=stnum[i];j++){for(int k=1;k<=stnum[i-1];k++){int mmax=0;if(state[i][j]&state[i-1][k]) continue;for(int s=1;s<=stnum[i-2];s++){if((state[i][j]&state[i-2][s])||(state[i-1][k]&state[i-2][s])) continue;mmax=max(mmax,dp[i-1][k][s]);}dp[i][j][k]=mmax+sum[state[i][j]];}}int ans=-1;for(int i=1;i<=stnum[n];i++)for(int j=1;j<=stnum[n-1];j++)ans=max(ans,dp[n][i][j]);printf("%d\n",ans);}return 0;}
一个人的期望值越大，心理承受力就会越小，就越经受不住失败的打击，
