[子集枚举+思维]2018 Multi-University Contest 10 J. 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)
$S_{MW}+S_{SW}+{\sum }_{i=1}^k|x_{M{W}_i}?x_{S{W}_i}|$
Now you have to choose your best Main Weapon & Secondary Weapon and output the maximum evaluation.

翻译

输入$S_{MW},S_{SW}$,$x_{M{W}_i}$,$x_{S{W}_i}$,$k$.
MW为主件,有$n$个，SW为附件，有$m$个。
求$S_{MW}+S_{SW}+{\sum }_{i=1}^k|x_{M{W}_i}?x_{S{W}_i}|$的最大值

题解

算是一道比较简单的题目吧qwq.
题目要求求$S_i+S_j+{\sum }_{p=1}^k|x_{i,p}?y_{j,p}|$的最大值。
实际上$S_i+S_j$的最大值十分好求，找两个最大的$S$即可。
但${\sum }_{p=1}^k|x_{i,p}?y_{j,p}|$这一部分十分不友好。
因此我们想办法将这个绝对值去掉。
注意题目要求我们求最大的绝对值。
我们应先考虑一个子问题:

求$|a_i?b_j|$的最大值

注意到$|a?b|=max(a?b,b?a)$
那么$max(|a_i?b_j|)=max(max(a_i?b_j,b_j?a_i))=max(a_i?b_j,b_j?a_i)=max(a_i,?a_i)+min(b_j,?b_j)$
解释一下这一步…$max(a_i,?a_i)$一定是非负的，$min(b_j,?b_j)$一定是非正的。
这一步相当于将$a_i$全部强制为正，$b_i$全部强制为负然,后找最大值求和
。（至于为什么我真的讲不清楚啊qwq）
等价于$max(a_i,?a_i)?max(b_j,?b_j)$

如果是求$|a_{i,1}?b_{j,1}|+|a_{i,2}?b_{j,2}|$.
很明显就是$max(a_{i,1}+a_{i,2},?a_{i,1}?a_{i,2},?a_{i,1}+a_{i,2},a_{i,1}?a_{i,2})?max(b_{j,1}+b_{j,2},?b_{j,1}?b_{j,2},b_{j,1}?b_{j,2},?b_{j,1}+b_{j,2})$

那么对于${\sum }_{p=1}^k|x_{i,p}?y_{j,p}|$就是
$max(max(({\sum }_{p=1}^k\pm x_{i,p}))+max(max({\sum }_{p=1}^k\pm y_{j,p}))$
对与±号，我们可以用子集枚举来完成。
答案$S_i+S_j+{\sum }_{p=1}^k|x_{i,p}?y_{j,p}|$就是
$max((max(({\sum }_{p=1}^k\pm x_{i,p})+S_i))+max((max({\sum }_{p=1}^k\pm y_{j,p})?S_j))$
(抱歉，这道题实在讲的太不清楚了)
复杂度$O(n?2^k)$
放上官方题解:

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;
#define MAXN 100000
#define INF 100000000000
int T,n,m,k;
long long S1[MAXN+5],S2[MAXN+5];
long long a[MAXN+5][6];
long long b[MAXN+5][6];
long long ans;
int main()
{
    scanf("%d",&T);while(T--){
    ans=0;scanf("%d%d%d",&n,&m,&k);for(int i=0;i<n;i++){
    scanf("%lld",&S1[i]);for(int j=0;j<k;j++)scanf("%lld",&a[i][j]);}for(int i=0;i<m;i++){
    scanf("%lld",&S2[i]);for(int j=0;j<k;j++)scanf("%lld",&b[i][j]);}for(int S=0;S<(1<<k);S++){
    long long maxx=-INF,minn=INF;for(int i=0;i<n;i++){
    long long p1=S1[i];for(int j=0;j<k;j++)if(S&(1<<j))p1+=a[i][j];else p1-=a[i][j];//printf("%lld\n",p1);maxx=max(maxx,p1);}for(int i=0;i<m;i++){
    long long p1=-S2[i];for(int j=0;j<k;j++)if(S&(1<<j))p1+=b[i][j];else p1-=b[i][j];//printf("%lld\n",p1);minn=min(minn,p1);}ans=max(ans,maxx-minn);}printf("%lld\n",ans);}
}