本文主要是介绍炮兵阵地 POJ - 1185，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
点击打开链接
第i行只和第i-1行 第i-2行有关 显然要DP 发现列数很小 考虑状态压缩 但若使dp[i][j][k]代表在第i行 第i行取j状态 第i-1行取k状态 那复杂度就是n*(2^m)*(2^m)*(2^m)
这里最巧妙的是 对于某一行 它所有状态中 满足炮兵两两不交叉的状态非常少 因为这相当于要求二进制位上相邻1至少相隔两位 这样就把m变的很小 最后注意一下细节
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=20;
const int maxm=1e2+10;int dp[maxm][maxm][maxm];
int pre[maxm],cnt[maxm],val[maxm];
int n,m,num;bool judge(int a,int b)
{if(a&b) return 0;else return 1;
}void init()
{int i,t;num=0;for(i=0;i<(1<<m);i++){if(judge(i,i<<1)&&judge(i,i<<2)){pre[num]=i;t=i,cnt[num]=0;while(t>0){cnt[num]+=t%2;t/=2;}num++;}}
}int solve()
{int res,i,j,k,l;memset(dp,0,sizeof(dp));for(i=0;i<num;i++){if(judge(pre[i],val[1])){dp[1][i][0]=cnt[i];}}for(i=2;i<=n;i++){for(j=0;j<num;j++){for(k=0;k<num;k++){for(l=0;l<num;l++){if(judge(pre[j],pre[k])&&judge(pre[k],pre[l])&&judge(pre[l],pre[j])&&judge(pre[j],val[i])&&judge(pre[k],val[i-1])&&judge(pre[l],val[i-2])){dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][l]+cnt[j]);}}}}}res=0;for(i=0;i<num;i++){for(j=0;j<num;j++){res=max(res,dp[n][i][j]);}}return res;
}int main()
{char ch[maxn];int i,j;while(scanf("%d%d",&n,&m)!=EOF){init();for(i=1;i<=n;i++){scanf("%s",ch);val[i]=0;for(j=0;j<m;j++){if(ch[j]=='H'){val[i]+=(1<<j);}}}printf("%d\n",solve());}return 0;
}
这篇关于炮兵阵地 POJ - 1185的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
