Problem J. CSGO

来源

2018杭电多校第十场

题意

游戏提供了 件主武器和 件副武器，每件武器有一个攻击力 ，还有 个子属性 。要从武器库里面选择一件主武器和一件副武器，请选择出攻击力和及各项属性值差异和最大的两件武器。

数学表示为：

解题思路

因为需要从主武器和副武器里挑出一个。对于属性的差值，最好的方法肯定是一个最大的减去最小的。所以可以这样考虑，对于每种属性，它对答案的贡献，要么是加上它，
要么是减去它，所以只要枚举每种属性的加减状态就行，对于主武器的s，和副武器的s，也可以将他们考虑进来，只要将他们的位置错开（这样就可以保证他们不会相减了），
由于 ，也就是说主武器和副武器的各个属性前面的符号是相反的，属性数量很少，可以枚举出所有的情况选出一个最优的就是答案。
我们通过枚举子集，子集对应二进制位为1时进行加法操作，子集对应的二进制位为0时进行减法操作，来枚举每件武器采用不同的加减策略对攻击值的贡献，找到贡献最大的那两个武器。

代码

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
int a[maxn][6], b[maxn][6];

int n,m,k;
ll ans, sum;

int main() {
    int t; scanf("%d",&t);
    while(t--) {
        ans=0; sum=0;
        scanf("%d%d%d",&n,&m,&k);
        for(int i=0;i<n;i++)
            for(int j=0;j<=k;j++)
                scanf("%d",&a[i][j]);
        for(int i=0;i<m;i++)
            for(int j=0;j<=k;j++)
                scanf("%d",&b[i][j]);
        for(int i=0;i<(1<<k);i++) {
            ll mx1=-2e18, mx2=-2e18;
            for(int j=0;j<n;j++) {
                sum=0;
                sum+=a[j][0];
                for(int l=1;l<=k;l++)
                    if(((i>>(l-1))&1)==1) sum+=a[j][l];
                    else sum-=a[j][l];
                mx1=max(mx1, sum);
            }
            for(int j=0;j<m;j++) {
                sum=0;
                sum+=b[j][0];
                for(int l=1;l<=k;l++)
                    if(((i>>(l-1))&1)==1) sum-=b[j][l];
                    else sum+=b[j][l];
                mx2=max(mx2, sum);
            }
            ans = max(ans, mx1+mx2);
        }
        printf("%lld\n",ans);
    }
}