题目描述
You are playing CSGO.
There are n Main Weapons and m Secondary Weapons in CSGO. You can only choose one Main Weapon and one Secondary Weapon. For each weapon, it has a composite score S.
The higher the composite score of the weapon is, the better for you.
Also each weapon has K performance evaluations x[1], x[2], …, x[K].(range, firing rate, recoil, weight…)
So you shold consider the cooperation of your weapons, you want two weapons that have big difference in each performance, for example, AWP + CZ75 is a good choose, and so do AK47 + Desert Eagle.
All in all, you will evaluate your weapons by this formula.(MW for Main Weapon and SW for Secondary Weapon)
Now you have to choose your best Main Weapon & Secondary Weapon and output the maximum evaluation.
输入
Multiple query.
On the first line, there is a positive integer T, which describe the number of data. Next there are T groups of data.
for each group, the first line have three positive integers n, m, K.
then, the next n line will describe n Main Weapons, K+1 integers each line S, x[1], x[2], …, x[K]
then, the next m line will describe m Secondary Weapons, K+1 integers each line S, x[1], x[2], …, x[K]
There is a blank line before each groups of data.
T<=100, n<=100000, m<=100000, K<=5, 0<=S<=1e9, |x[i]|<=1e9, sum of (n+m)<=300000
输出
Your output should include T lines, for each line, output the maximum evaluation for the corresponding datum.
样例输入
2
2 2 1
0 233
0 666
0 123
0 456
2 2 1
100 0 1000 100 1000 100
100 0
样例输出
543
2000
题意：
就是给你一堆主武器和副武器，然后挑选其中综合得分最高的（主副武器本身分值高，且差值最大），计算公式如上。
思路：
既然要挑选武器，最好的方法就是最大的减去最小的。所以，可以这么考虑，对于每一种属性，它对于答案的贡献，要么是加，要么是减
所以可以通过二进制枚举，枚举每一种状态，对于主武器的s，和副武器的s，将他们考虑进来，将他们的位置错开保证他们不会相减,即
主s设在0位置，副武器s设在1位置，所以共k+2个属性，也就是2^(k+2)种枚举。
代码：
1 #include <iostream>
2 #include <bits/stdc++.h>
3 using namespace std;
4 const int maxn = 1e5+
50;
5 typedef
long long ll;
6 int n,m,k,top;
7 ll ma[maxn][
10],se[maxn][
10];
8 ll maxv1,minv1,maxv2,minv2;
9 ll all;
10 void read1()
11 {
12 for(
int i=
0; i<n; i++
)
13 {
14 scanf(
"%lld",&ma[i][
0]);
15 for(
int j=
0; j<k; j++
)
16 {
17 scanf(
"%lld",&ma[i][j+
2]);
18 }
19 }
20 }
21 void read2()
22 {
23 for(
int i=
0; i<m; i++
)
24 {
25 scanf(
"%lld",&se[i][
1]);
26 for(
int j=
0; j<k; j++
)
27 {
28 scanf(
"%lld",&se[i][j+
2]);
29 }
30 }
31 }
32 void solve1()
33 {
34 for(
int q=
0; q<top; q++
)
35 {
36 maxv1=-1e18,minv1=
1e18;
37 maxv2=-1e18,minv2=
1e18;
38 for(
int i=
0; i<n; i++
)
39 {
40 ll temp=
0;
41 for(
int j=
0; j<k+
2; j++
)
42 {
43 if(q&(
1<<
j))
44 {
45 temp+=
ma[i][j];
46 }
47 else
48 {
49 temp-=
ma[i][j];
50 }
51 }
52 maxv1=
max(maxv1,temp);
53 minv1=
min(minv1,temp);
54 }
55 for(
int i=
0; i<m; i++
)
56 {
57 ll temp=
0;
58 for(
int j=
0; j<k+
2; j++
)
59 {
60 if(q&(
1<<
j))
61 {
62 temp+=
se[i][j];
63 }
64 else
65 {
66 temp-=
se[i][j];
67 }
68 }
69 maxv2=
max(maxv2,temp);
70 minv2=
min(minv2,temp);
71 }
72 ll maxx=max(maxv1-minv2,maxv2-
minv1);
73 all=
max(all,maxx);
74 }
75 }
76 int main()
77 {
78 int T;
79 cin>>
T;
80 while(T--
)
81 {
82 scanf(
"%d%d%d",&n,&m,&
k);
83 read1();
84 read2();
85 all=
0;
86 top=
1<<(k+
2);
87 solve1();
88 //solve2();
89 cout << all <<
endl;
90 }
91 //cout << "Hello world!" << endl;
92 return 0;
93 }
94 /*
95 2
96 2 2 1
97 0 233
98 0 666
99 0 123
100 0 456
101 2 2 1
102 100 0 1000 100 1000 100
103 100 0
104 */
105 /*
106 546
107 2000
108 */
View Code
转载于:https://www.cnblogs.com/SoulSecret/p/9524968.html
相关资源：垃圾分类数据集及代码
