题意:

三堆石子,你可以取两堆石子各一个石头a,b。然后消掉a,使得b=b-a再放入b的那一堆。这样操作直到只剩下一个石子,求该石子价值最大。

题解:

构造题
可以构造出两者情况:

  1. 其中两堆都是正的,一堆都是负的
  2. 一个背包都是正的,另两个背包的最小值是负的,其他都是正的
    为什么是这样构造出来的呢?
    参考题解
    对于一个数如果进行奇数次操作,那么就是负贡献,偶数次操作就是正贡献
    假设最后一个数在数组a,那么a中剩下n-1个数,可以在最后先与其他数组合并,再和最后一个数合并,这样就都是正贡献。同理应用到b和c数组,就相当于b,c中只有一个数的负贡献,其他都是正,我们取b,c中最小的为负贡献
    或者我们直接选b,c中一个数组为正数组,另一个为负数组

    代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 300010;

int n1, n2, n3;
ll a[maxn], b[maxn], c[maxn];
ll s1, s2, s3;
ll m1, m2, m3;

ll ans = 0;

ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * f; }

int main(){
    n1 = read(), n2 = read(), n3 = read();
    for(int i = 1 ; i <= n1 ; ++i) a[i] = read(), s1 += a[i];
    for(int i = 1 ; i <= n2 ; ++i) b[i] = read(), s2 += b[i];
    for(int i = 1 ; i <= n3 ; ++i) c[i] = read(), s3 += c[i];

    ans = -1e18;

    ans = max(ans, s1 + s2 - s3); 
    ans = max(ans, s2 + s3 - s1);
    ans = max(ans, s3 + s1 - s2);

    m1 = a[1], m2 = b[1], m3 = c[1];

    for(int i = 2 ; i <= n1 ; ++i) m1 = min(m1, a[i]);
    for(int i = 2 ; i <= n2 ; ++i) m2 = min(m2, b[i]);
    for(int i = 2 ; i <= n3 ; ++i) m3 = min(m3, c[i]);

    ans = max(ans, s1 + s2 + s3 - 2 * m1 - 2 * m2);
    ans = max(ans, s1 + s2 + s3 - 2 * m1 - 2 * m3);
    ans = max(ans, s1 + s2 + s3 - 2 * m2 - 2 * m3);

    printf("%lld\n", ans);

    return 0;
}