代码提供者：SpringWater(GHQ) 题目大意：从该矩阵中的选出一些数字，使得和最大，但要保证，相邻（上下左右和对角线）的不能同时取出； 解题思路：预先把一行中，合法（不出现”11“）的状态S1算出来，再在此基础上，将该合法状态， 与其他合法状态互溶的状态S2算出来，放在该状态后面，之后，dp每一行进行状态转移：dp[i][S1]=val[S1]+sum{dp[i-1][S2]}; #include #include #include using namespace std;vector rem[16][1600];int cntrem[16];int map[16][16];int val[32868];int dp[2][32868];void inite(){ int i,up,temp,cas,j; for(cas=3;cas<=15;cas++){ cntrem[cas]=0; up=1< >=1; } if(temp)continue; ++cntrem[cas]; rem[cas][cntrem[cas]].clear(); rem[cas][cntrem[cas]].push_back(i); } for(i=1;i >=1; } if(temp)continue; rem[cas][i].push_back(rem[cas][j][0]); rem[cas][j].push_back(rem[cas][i][0]); } } }}int main(){ int cnt,i,j,t,now,pre,m,k,ans,temp; char ch; freopen("in.txt","r",stdin); inite(); while(~scanf("%d%c",&map[1][1],&ch)) { if(ch!='\n') { cnt=1; while(scanf("%d%c",&map[1][++cnt],&ch)&&(ch!='\n')); for(i=2;i<=cnt;i++){ for(j=1;j<=cnt;j++) scanf("%d%c",&map[i][j],&ch); } for(j=1;j<=cntrem[cnt];j++){ temp=rem[cnt][j][0]; val[rem[cnt][j][0]]=0; t=1; while(temp){ if(temp&1) val[rem[cnt][j][0]]+=map[1][t]; temp>>=1; t++; } } pre=1,now=0; for(i=1;i<=cntrem[cnt];i++) dp[pre][rem[cnt][i][0]]=val[rem[cnt][i][0]]; for(i=2;i<=cnt;i++,pre=!pre,now=!now) { for(j=1;j<=cntrem[cnt];j++) { temp=rem[cnt][j][0]; val[rem[cnt][j][0]]=0; t=1; while(temp) { if(temp&1) val[rem[cnt][j][0]]+=map[i][t]; temp>>=1; t++; } } for(j=1;j<=cntrem[cnt];j++) { m = rem[cnt][j].size(); dp[now][rem[cnt][j][0]] = val[rem[cnt][j][0]]; temp = 0; for(k=1;k temp)temp=dp[pre][rem[cnt][j][k]]; } dp[now][rem[cnt][j][0]]+=temp; } } ans=0; for(i=1;i<=cntrem[cnt];i++){ if(dp[pre][rem[cnt][i][0]]>ans)ans=dp[pre][rem[cnt][i][0]]; } printf("%d\n",ans); } else printf("%d\n",map[1][1]); scanf("%c",&ch); } return 0;}