本文主要是介绍hdu 2167，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
//状态压缩DP
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;const int N=17, M=1600;
int map[N][N], p[N], val[M][N], dp[N][M], sum[N][M];
vector<int> mat[M];
int n,num,ans;void Make()
{memset(p,0,sizeof(p));int i,j,m,tmp,x;num=0;m=(1<<n)-1;for(i=0;i<=m;i++){tmp=n; x=i;while(x){p[tmp--]=x%2;x/=2;}for(j=2;j<=n;j++)if(p[j] && p[j-1]) break;if(j==n+1){for(j=1;j<=n;j++)val[num][j]=p[j];num++;}}
}bool check(int *a, int *b)
{for(int i=1;i<=n;i++)if(a[i] && (b[i-1] || b[i] || b[i+1])) return 0;return 1;
}void init()
{int i,j,k;memset(sum,0,sizeof(sum));for(i=0;i<num;i++)for(j=i+1;j<num;j++)if( check(val[i], val[j]) ){mat[i].push_back(j);mat[j].push_back(i);}for(i=1;i<=n;i++)for(j=0;j<num;j++)for(k=1;k<=n;k++) sum[i][j]+=val[j][k]*map[i][k];
}void solve()
{int i,j,k,cur;memset(dp,0,sizeof(dp));for(i=1;i<=n;i++)for(j=0;j<num;j++){int m=mat[j].size();for(k=0;k<m;k++){cur=mat[j][k];dp[i][j]=max(dp[i][j], dp[i-1][cur]+sum[i][j]);}}ans=0;for(i=0;i<num;i++) ans=max(ans,dp[n][i]);
}int main()
{// freopen("in","r",stdin);// freopen("out","w",stdout);char s[100];int tmp,i,j,len,m,k=1;while(gets(s)!=NULL){len=strlen(s);n=(len+1)/3;for(i=0,j=1;i<len;i+=3)map[1][j++]=10*(s[i]-'0')+s[i+1]-'0';for(k=2;k<=n;k++){gets(s);for(i=0,j=1;i<len;i+=3)map[k][j++]=10*(s[i]-'0')+s[i+1]-'0';}getchar();Make();init();solve();printf("%d\n",ans);}return 0;
}这篇关于hdu 2167的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
