大致题意
天哪最近hdu系统晚上一直维护看不了题面… 大概说下：给 n 个主武器，m 个副武器，每个武器有个价值s[i]。每个武器有 k 种表现，现要求你选择一把主武器和一把副武器。使得他们的价值和val最大，val的计算方式如下。 val = s[i] + s[j] + （ i 和 j 在 k 种表现下的绝对值之差的和） 范围： 1<=n,m<=1e5, 1<=k<=5
思路
可以把上面的 m 个副武器的价值s[j] 看成是一种表现，那么就有 k+1 种表现值，把主武器对应位置的值设成 0，那么对于每个主武器 i 的搭配最大价值 val 就等于 s[i] + （与副武器在k+1维上的最大曼哈顿距离）。 对于k比较小的时候求解曼哈顿距离有一种套路的方法，二进制枚举绝对值符号的展开结果。例如 |x1 - x2| + |y1 - y2|，枚举绝对值展开的结果就是：
x1 - x2 + y1 - y2
x1 - x2 + y2 - y1
x2 - x1 + y1 - y2
x2 - x1 + y2 - y1 变形一下就是：
(x1 + y1) - (x2 + y2)
(x1 - y1) - (x2 - y2)
(-x1 + y1) - (-x2 + y2)
(-x1 - y1) - (-x2 - y2) 以上4种结果中取最大即为曼哈顿距离。 因此我们可以先对m种副武器进行 (1<<K)种可能进行预处理，求出每种状态的最小值，然后对于每种主武器只要算出相应的值，减去最小，然后这（1<<K)种状态取个最大即可。
代码
#include<bits/stdc++.h>
using namespace std
;
#define maxn 100006
#define maxm 1006
#define ll long long int
#define INF 0x3f3f3f3f
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
#define mem(a) memset(a,0,sizeof(a))
#define sqr(x) (x*x)
#define inf (ll)2e18+1
#define PI acos(-1)
#define mod 10007
#define auto(i,x) for(int i=head[x];i;i=ed[i].nxt)
#define ls x<<1
#define rs x<<1|1
ll
read(){
ll x
=0,f
=1ll;char ch
=getchar();
while(!isdigit(ch
)){if(ch
=='-')f
=-1;ch
=getchar();}
while(isdigit(ch
))x
=x
*10+ch
-'0',ch
=getchar();
return f
*x
;
}
int T
,n
,m
,k
;
int a
[maxn
],b
[maxn
];
int k1
[maxn
][10],k2
[maxn
][10];
ll val
[100];
int main()
{
T
=read();
while(T
--){
n
=read();m
=read();k
=read();
inc(i
,1,n
){
a
[i
]=read();
k1
[i
][0]=0;
inc(j
,1,k
)k1
[i
][j
]=read();
}
inc(i
,1,m
){
b
[i
]=read();
k2
[i
][0]=b
[i
];
inc(j
,1,k
)k2
[i
][j
]=read();
}
k
++;
int up
=(1<<k
)-1;
inc(i
,0,up
)val
[i
]=inf
;
inc(r
,1,m
)inc(i
,0,up
){
ll res
=0;
inc(j
,0,k
-1){
if((i
&(1<<j
)))res
-=1ll*k2
[r
][j
];
else res
+=1ll*k2
[r
][j
];
}
val
[i
]=min(val
[i
],res
);
}
ll ans
=-inf
;
inc(r
,1,n
){
ll tmp
=-inf
;
inc(i
,0,up
){
ll res
=0;
inc(j
,0,k
-1){
if((i
&(1<<j
)))res
-=1ll*k1
[r
][j
];
else res
+=1ll*k1
[r
][j
];
}
tmp
=max(tmp
,res
-val
[i
]);
}
ans
=max(ans
,tmp
+a
[r
]);
}
printf("%lld\n",ans
);
}
return 0;
}
