首页 > 代码库 > nefu1109 游戏争霸赛(状压dp)
nefu1109 游戏争霸赛(状压dp)
题目链接:http://acm.nefu.edu.cn/JudgeOnline/problemShow.php?problem_id=1109
//我们校赛的一个题,状压dp,还在的人用1表示,被淘汰的人用0表示。倒着循环即可。
//比赛的时候我用的是二维dp数组表示状态,一直是WA的,搞不懂原因。。。Orz。。。
代码:
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #define ll long long using namespace std; const int INF=0x3f3f3f3f; const int maxn=50005; int dp[1<<11]; ///dp用一维就能表示状态 int d[15][15]; int main() { int n; while(scanf("%d",&n)==1) { for(int i=0; i<n; i++) for(int j=0; j<n; j++) scanf("%d",&d[i][j]); memset(dp,0,sizeof(dp)); for(int i=(1<<n)-1; i>=1; i--) { for(int j=0; j<n; j++) { int tmp=(1<<j); if(i&tmp) { for(int k=0; k<n; k++) { if((1<<k)&i) continue; dp[i]=max(dp[i],dp[i^(1<<k)]+d[j][k]); } } } } int ans=-INF; for(int i=0; i<n; i++) ans=max(ans,dp[1<<i]); printf("%d\n",ans); } return 0; }
nefu1109 游戏争霸赛(状压dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。