[子集枚举+思维]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)
SMW+SSW+∑i=1k∣xMWi−xSWi∣S_{MW}+S_{SW}+sum^{k}_{i=1} vert x_{MW_i}-x_{SW_i} vertSMW​+SSW​+∑i=1k​∣xMWi​​−xSWi​​∣
Now you have to choose your best Main Weapon & Secondary Weapon and output the maximum evaluation.

翻译

输入SMW,SSWS_{MW},S_{SW}SMW​,SSW​,xMWix_{MW_i}xMWi​​,xSWix_{SW_i}xSWi​​,$k$.
MW为主件,有$n$个，SW为附件，有$m$个。
求SMW+SSW+∑i=1k∣xMWi−xSWi∣S_{MW}+S_{SW}+sum^{k}_{i=1} vert x_{MW_i}-x_{SW_i} vertSMW​+SSW​+∑i=1k​∣xMWi​​−xSWi​​∣的最大值

题解

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

求∣ai−bj∣vert a_i-b_j vert∣ai​−bj​∣的最大值

注意到$|a-b|=max(a-b,b-a)$
那么max(∣ai−bj∣)=max(max(ai−bj,bj−ai))=max(ai−bj,bj−ai)=max(ai,−ai)+min(bj,−bj)max(vert a_i-b_j vert)=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(∣ai​−bj​∣)=max(max(ai​−bj​,bj​−ai​))=max(ai​−bj​,bj​−ai​)=max(ai​,−ai​)+min(bj​,−bj​)
解释一下这一步…max(ai,−ai)max(a_i,-a_i)max(ai​,−ai​)一定是非负的，min(bj,−bj)min(b_j,-b_j)min(bj​,−bj​)一定是非正的。
这一步相当于将aia_iai​全部强制为正，bib_ibi​全部强制为负然,后找最大值求和
。（至于为什么我真的讲不清楚啊qwq）
等价于max(ai,−ai)−max(bj,−bj)max(a_i,-a_i)-max(b_j,-b_j)max(ai​,−ai​)−max(bj​,−bj​)

如果是求∣ai,1−bj,1∣+∣ai,2−bj,2∣vert a_{i,1}-b_{j,1} vert+vert a_{i,2}-b_{j,2} vert∣ai,1​−bj,1​∣+∣ai,2​−bj,2​∣.
很明显就是max(ai,1+ai,2,−ai,1−ai,2,−ai,1+ai,2,ai,1−ai,2)−max(bj,1+bj,2,−bj,1−bj,2,bj,1−bj,2,−bj,1+bj,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})max(ai,1​+ai,2​,−ai,1​−ai,2​,−ai,1​+ai,2​,ai,1​−ai,2​)−max(bj,1​+bj,2​,−bj,1​−bj,2​,bj,1​−bj,2​,−bj,1​+bj,2​)

那么对于∑p=1k∣xi,p−yj,p∣sum^{k}_{p=1} vert x_{i,p}-y_{j,p} vert∑p=1k​∣xi,p​−yj,p​∣就是
max(max((∑p=1k±xi,p))+max(max(∑p=1k±yj,p))max(max((sum^{k}_{p=1} ±x_{i,p}) )+max(max(sum^{k}_{p=1} ±y_{j,p}))max(max((∑p=1k​±xi,p​))+max(max(∑p=1k​±yj,p​))
对与±号，我们可以用子集枚举来完成。
答案Si+Sj+∑p=1k∣xi,p−yj,p∣S_i+S_j+sum^{k}_{p=1} vert x_{i,p}-y_{j,p} vertSi​+Sj​+∑p=1k​∣xi,p​−yj,p​∣就是
max((max((∑p=1k±xi,p)+Si))+max((max(∑p=1k±yj,p)−Sj))max((max((sum^{k}_{p=1} ±x_{i,p})+S_i) )+max((max(sum^{k}_{p=1} ±y_{j,p})-S_j))max((max((∑p=1k​±xi,p​)+Si​))+max((max(∑p=1k​±yj,p​)−Sj​))
(抱歉，这道题实在讲的太不清楚了)
复杂度O(n∗2k)O(n*2^k)O(n∗2k)
放上官方题解:

代码

#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("%lldn",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("%lldn",p1);
minn=min(minn,p1);
}
ans=max(ans,maxx-minn);
}
printf("%lldn",ans);
}
}