题目描述
（看不清图片可以右击图片-> 复制图片地址 ->浏览器新开一个标签页，粘贴此地址就可看大图
（也可以右击图片-> 在新标签页打开图片
题解
题意： 给你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 <iostream>
#include <stack>
#include "algorithm"
#include "cstdio"
#include "queue"
#include "set"
#include "cstring"
#include "string"
#include "map"
#include "vector"
#include "math.h"
#include "utility"
#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
| 恰似你一低头的温柔，较弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。
|