題意：

三堆石子，你可以取兩堆石子各一個石頭a,b。然后消掉a，使得b=b-a再放入b的那一堆。這樣操作直到只剩下一個石子，求該石子價值最大。

題解：

構造題
可以構造出兩者情況：

其中兩堆都是正的，一堆都是負的

一個背包都是正的，另兩個背包的最小值是負的，其他都是正的
為什么是這樣構造出來的呢？
參考題解
對于一個數如果進行奇數次操作，那么就是負貢獻，偶數次操作就是正貢獻
假設最后一個數在數組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; }

總結

以上是生活随笔為你收集整理的Three Bags CodeForces - 1467C的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。