2019年牛客多校第二场 F题Partition problem 爆搜

秒速五厘米 2021-11-01 03:28 210阅读 0赞

# 题目链接 #

[传送门][Link 1]

# 题意 #

总共有\\(2n\\)个人，任意两个人之间会有一个竞争值\\(w\_\{ij\}\\)，现在要你将其平分成两堆，使得\\(\\sum\\limits\_\{i=1,i\\in\\mathbb\{A\}\}^\{n\}\\sum\\limits\_\{j=1,j\\in\\mathbb\{B\}\}^\{n\}w\_\{ij\}\\)最大。

# 思路 #

看到这一题第一想法是状态压缩然后枚举状态，然后人就没了。  
其实这题就是个普通的\\(dfs\\)，假设在枚举第\\(i\\)个人时，前面已经有\\(tot1\\)个人分进了\\(\\mathbb\{A\}\\)，\\(tot2\\)个人分进了\\(\\mathbb\{B\}\\)中，则

*  如果\\(tot1<n\\)，那么\\(i\\)可以放进\\(\\mathbb\{A\}\\)中，在放进去的时候将\\(sum\\)加上\\(i\\)与前\\(tot2\\)个人的竞争值；
 *  如果\\(tot2<n\\)，那么\\(i\\)可以放进\\(\\mathbb\{B\}\\)中，在放进去的时候将\\(sum\\)加上\\(i\\)与前\\(tot1\\)个人的竞争值。

在\\(tot1,tot2\\)都等于\\(n\\)时将\\(sum\\)与\\(ans\\)进行取\\(max\\)即可，复杂度为\\(O(nC\_\{2n\}^\{n\})\\)。

# 代码实现如下 #

#include <set> #include <map> #include <deque> #include <queue> #include <stack> #include <cmath> #include <ctime> #include <bitset> #include <cstdio> #include <string> #include <vector> #include <cassert> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #include <unordered_map> using namespace std; typedef long long LL; typedef pair<LL, LL> pLL; typedef pair<LL, int> pLi; typedef pair<int, LL> pil;; typedef pair<int, int> pii; typedef unsigned long long uLL; #define lson rt<<1 #define rson rt<<1|1 #define lowbit(x) x&(-x) #define name2str(name) (#name) #define bug printf("*********\n") #define debug(x) cout<<#x"=["<<x<<"]" <<endl #define FIN freopen("D://Code//in.txt","r",stdin) #define IO ios::sync_with_stdio(false),cin.tie(0) const double eps = 1e-8; const int mod = 1000000007; const int maxn = 1e5 + 7; const double pi = acos(-1); const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3fLL; LL ans; int n, tot1, tot2; int mp[30][30], a[30], b[30]; void dfs(int pos, LL sum) { if(tot1 > n || tot2 > n) return; if(tot1 == n && tot2 == n) { ans = max(ans, sum); return; } if(tot1 < n) { a[++tot1] = pos; for(int i = 1; i <= tot2; ++i) { sum += mp[pos][b[i]]; } dfs(pos + 1, sum); for(int i = 1; i <= tot2; ++i) { sum -= mp[pos][b[i]]; } --tot1; } if(tot2 < n) { b[++tot2] = pos; for(int i = 1; i <= tot1; ++i) { sum += mp[pos][a[i]]; } dfs(pos + 1, sum); for(int i = 1; i <= tot1; ++i) { sum -= mp[pos][a[i]]; } --tot2; } } int main() { #ifndef ONLINE_JUDGE FIN; #endif // ONLINE_JUDGE scanf("%d", &n); for(int i = 1; i <= 2 * n; ++i) { for(int j = 1; j <= 2 * n; ++j) { scanf("%d", &mp[i][j]); } } dfs(1, 0); printf("%lld\n", ans); return 0; }

转载于:https://www.cnblogs.com/Dillonh/p/11219011.html

[Link 1]: https://ac.nowcoder.com/acm/contest/882/F