HDUOJ 6435 Problem J. CSGO

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=6435

题意:略。

思路:现在回来看看这题发现就很水了。。。思路参见http://www.perfectpan.org/archives/2434,虽然多了一个属性S,但是不影响我们直接把它塞到每一个状态里,然后每个状态下的最远曼哈顿距离取max就是答案了。

#include <bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=32;
const ll INF=2000000000000000000LL;
int T,n,m,K,i,S;
ll ans,s,f[N],mx[N][2];
void go(int tp){
    read(s);
    for (int i=0;i<K;++i) read(f[i]);
    for (int status=0;status<=S;++status){
        ll ret=s;
        for (int i=0;i<K;++i) ret+=(status&(1<<i))?f[i]:-f[i];
        mx[status][tp]=max(mx[status][tp],ret);
    }
}
int main(){
    for (read(T);T--;){
        read(n),read(m),read(K),S=(1<<K)-1;
        for (i=0;i<=S;++i) mx[i][0]=mx[i][1]=-INF;
        for (i=1;i<=n;++i) go(0);
        for (i=1;i<=m;++i) go(1);
        ans=-INF;
        for (i=0;i<=S;++i) ans=max(ans,mx[i][0]+mx[i^S][1]);
        printf("%lld\n",ans);
    }
    return 0;
}