【hdu 6435】杭电多校：CSGO（曼哈顿距离+二进制枚举）

题目描述

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