题目概述

你在play♂CSGO，被第 $i$ 种枪打跪体现你有 $S_i$ 的手残值，并且有 $K$ 个参数 $\{x_{i,K}\}$ ，被第 $j$ 种刀捅挂体现你有 $S_j$ 的手残值，并且也有 $K$ 个参数 $\{y_{j,K}\}$ 。你每次都会被一种枪打跪之后用刀捅挂，这时候体现了你有 $S_i+S_j+\sum_{k=1}^{K}|x_{i,k}-y_{j,k}|$ 的手残值。请问你体现出的手残值最大为多少。

解题报告

一个套路，把绝对值看成 $max\{x-y,y-x\}$ ，由于要求值最大所以不合法的那种(负数)一定不会选，就可以达到去除绝对值的效果。

那么只需要 $2^K$ 枚举每个参数的正负情况，然后求 $max\{S_i+f_kx_{i,k}\}+max\{S_j-f_ky_{j,k}\}$ 的最大值就是答案。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100000;

int te,n,m,K,A[maxn+5],B[maxn+5],x[maxn+5][5],y[maxn+5][5];LL ans;

int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (scanf("%d",&te);te;te--){
        scanf("%d%d%d",&n,&m,&K);ans=0;
        for (int i=1;i<=n;i++) {scanf("%d",&A[i]);for (int j=0;j<K;j++) scanf("%d",&x[i][j]);}
        for (int i=1;i<=m;i++) {scanf("%d",&B[i]);for (int j=0;j<K;j++) scanf("%d",&y[i][j]);}
        for (int s=0;s<(1<<K);s++){
            LL MAXA=-(9e18),MAXB=-(9e18);
            for (int i=1;i<=n;i++){
                LL sum=A[i];for (int j=0;j<K;j++) if (s>>j&1) sum+=x[i][j]; else sum-=x[i][j];
                MAXA=max(MAXA,sum);
            }
            for (int i=1;i<=m;i++){
                LL sum=B[i];for (int j=0;j<K;j++) if (s>>j&1) sum-=y[i][j]; else sum+=y[i][j];
                MAXB=max(MAXB,sum);
            }
            ans=max(ans,MAXA+MAXB);
        }printf("%lld\n",ans);
    }
    return 0;
}