HDU 6435 Problem J. CSGO（水~）

Description

武器分主武器和副武器，每种武器有固定分数$S$和$k$个属性$x_1,...,x_k$，每次只能选一个主武器和一个副武器，两者搭配的分数为两者固定分数之和加上每项属性差的绝对值，问最高分数搭配

Input

第一行一整数$T$表示用例组数，每组用例首先输入三整数$n,m,k$表示主武器数量、副武器数量以及每种武器的属性数，之后$n+m$行输入$n$种主武器和$m$种副武器的固定分数和$k$种属性

$(1\le T\le 100,1\le n,m\le 10^5,1\le k\le 5,0\le S\le 10^9,|x_i|\le 10^9)$

Output

输出最高分数

Sample Input

2
2 2 1
0 233
0 666
0 123
0 456
2 2 1
100 0 1000 100 1000 100
100 0

Sample Output

543
2000

Solution

由于一件主武器的$k$种属性的在得分表示中的符号至多只有$2^k\le 32$种情况，而副武器的符号与这件武器的符号相反，故直接枚举这$2^k$种主武器符号，得到每种主武器和副武器在该种符号安排下的得分和，维护最大值即为答案

Code

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
#define maxn 100005
int T,n,m,k;
struct node
{
    int x[6],S;
    ll w;
}a[maxn],b[maxn];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&k);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i].S);
            for(int j=0;j<k;j++)scanf("%d",&a[i].x[j]);
        }
        for(int i=0;i<m;i++)
        {
            scanf("%d",&b[i].S);
            for(int j=0;j<k;j++)scanf("%d",&b[i].x[j]);
        }
        ll ans=-1e18;
        int K=1<<k;
        for(int S=0;S<K;S++)
        {
            int s1[6],s2[6];
            for(int i=0;i<k;i++)
                if((S>>i)&1)s1[i]=1,s2[i]=-1;
                else s1[i]=-1,s2[i]=1;
            ll ma=-1e18,mb=-1e18;
            for(int i=0;i<n;i++)
            {
                a[i].w=a[i].S;
                for(int j=0;j<k;j++)a[i].w+=s1[j]*a[i].x[j];
                ma=max(ma,a[i].w);
            }
            for(int i=0;i<m;i++)
            {
                b[i].w=b[i].S;
                for(int j=0;j<k;j++)b[i].w+=s2[j]*b[i].x[j];
                mb=max(mb,b[i].w);
            }
            ans=max(ans,ma+mb);
        }
        printf("%lld\n",ans);
    }
    return 0;
}