题目描述

(看不清图片可以右击图片-> 复制图片地址 ->浏览器新开一个标签页,粘贴此地址就可看大图
(也可以右击图片-> 在新标签页打开图片

F

题解

题意: 给你2 * n个人, 以及他们之间的竞争值(用矩阵表示),让你分成两组, 每组n个人, 问你如何分才能让竞争值最大(同队之间不存在竞争), 输出最大竞争值 。

分析: 用dfs爆搜, 从1开始, 当groupA 组员数小于n时, 就可以放进A, 同理groupB也是。最后当搜索到第 2 * n + 1时return。

ac代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//#include <bits/stdc++.h>
#include <iostream>
#include <stack>
#include "algorithm"
#include "cstdio"
#include "queue"
#include "set"
#include "cstring"
#include "string"
#include "map"
#include "vector"
#include "math.h"
#include "utility" // pair头文件
#define esp 1e-6
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 5;
ll val[102][102];
int n;
ll ans;
int group1[102], group2[102];

void dfs(int cur, int cnt1, int cnt2, ll sum){
if (cur >= 2 * n + 1){
ans = max(ans, sum);
return;
}

if (cnt1 < n){
ll tem = sum;
group1[cnt1 + 1] = cur;
for (int i = 1; i <= cnt2; i++)
tem += val[group2[i]][cur];
dfs(cur + 1, cnt1 + 1, cnt2, tem);
}

if (cnt2 < n){
ll tem = sum;
group2[cnt2 + 1] = cur;
for (int i = 1; i <= cnt1; i++){
tem += val[group1[i]][cur];
}
dfs(cur + 1, cnt1, cnt2 + 1, tem);
}

}

int main(){
cin >> n;
for (int i = 1; i <= 2 * n; i++){
for (int j = 1; j <= 2 * n; j++){
cin >> val[i][j];
}
}
dfs(1, 0, 0, 0);
cout << ans << "\n";
}
1
恰似你一低头的温柔,较弱水莲花不胜寒风的娇羞, 我的心为你悸动不休。  --mingfuyan