本文共 1700 字，大约阅读时间需要 5 分钟。
题解：二进制压缩，枚举每行存在的状态，判断与前一行的状态的关系，找出最大值
dp[i][j][k] = max(dp[i][j][k] , dp[i-1][k][[l] + p[j]) 表示第i行第j个状态,i-1行的第k个状态炮兵的最大数量
#include #include #include #include using namespace std;int dp[105][70][70];char map[105][20];int a[105];int s[70],p[70];int n,m,num;bool ok(int x){ if(x&(x<<1)) return false; //如果x的二进制里存在为类似于 11 则不满足 if(x&(x<<2)) return false; //如果x的二进制里存在为类似于 101或11，则不满足 return true;}void init(){//求解多少种符合的状态 num = 0; for(int i = 0;i < (1< <= n;i++){ scanf("%s",map[i]+1); a[i] = 0; for(int j = 1;j <= m;j++){ if(map[i][j] == 'H') a[i] +=(1<<(j-1));//记录每一行有山地的状态 } } memset(dp,0,sizeof(dp)); memset(p,0,sizeof(p)); for(int i = 1;i <= num;i++){ p[i] = cal(s[i]); //p[i] 存储每种状态的的山地的个数 if(find(s[i],1)) dp[1][i][1] = p[i]; //判定此状态下是否与存在山地的状态矛盾 } for(int i = 2;i <= n;i++){ for(int j= 1;j <= num;j++){ if(!find(s[j],i)) continue; for(int k = 1;k <= num;k++){ if(s[k]&s[j]) continue; for(int l = 1;l <= num;l++){ if(s[l]&s[j]) continue;// if(dp[i-1][j][k] == -1) continue; dp[i][j][k] = max(dp[i][j][k],dp[i-1][k][l] + p[j]); //用第i行的状态为j，第i-1行状态为k时的值 } } } } int ans = 0; for(int i = 1;i <= num;i++){ for(int j = 1;j <= num;j++){ ans = max(ans,dp[n][i][j]); } } printf("%d\n",ans); }}
转载地址：http://kdsgi.baihongyu.com/