首页 > 代码库 > UESTC1608 暑假集训
UESTC1608 暑假集训
题意:n个人(n<21),每三个人都有一个配合度,问最多配合度是多少?
题解:最多21个人,用二进制表示,每一个人1代表选了,0代表没有选,记忆化搜索+减枝
#include<bits/stdc++.h>using namespace std;int dp[1<<21], n, p[22][22][22];int dfs(int s){ if(dp[s] != -1) return dp[s]; int i= 0; for(i=0;i<=n-3;i++) if(s&(1<<i)) break;//会重复 for(int j=i+1;j<=n-2;j++) if(s&(1<<j)) for(int k=j+1;k<=n-1;k++) if(s&(1<<k)) dp[s] = max(dp[s], dfs(s^(1<<j)^(1<<i)^(1<<k))+p[i][j][k]); return dp[s];}int main(){ int a,b,c,w; cin>>n; int l = n*(n-1)*(n-2)/6; for(int i=0;i<l;i++){ cin>>a>>b>>c>>w; p[a-1][b-1][c-1] = w; } memset(dp, -1, sizeof(dp)); dp[0] = 0; cout<<dfs((1<<n)-1)<<endl; return 0;}
UESTC1608 暑假集训
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。