Codeforces Round 1049 (Div. 2)C. Ultimate Value

经过分析可知,游戏最多持续俩回合就必须结束是最优的
计算增量:
一共有5种case:

1. alice直接end,没有可以改变的空间
2. '-' '-'互换 只需要计算r-l即可,可以单独处理,区分n是奇数和偶数的情况
3. '+' '+'互换
4. '-' '+'互换 需要你计算derta: 这种case是:+2al -2ar +r-l:---->变形后 (2al-l)-(2ar-r);因为左边是先迭代,我们可以计算前i个的是偶数的时候最大的L式,当遍历到奇数位时,在使用mx求最大值
5. '+' '-'互换 case5只需要颠倒即可, -2al-l +2ar+r:---->变形后 -(2al+l)+(2ar+ar),遍历到奇数位时只需要求al的最小值,遍历到偶数位时,求mx维护最大值即可

点击查看代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;           // constexpr 0LL
using ull = unsigned long long; // constexpr 0ULL
using ui = unsigned int;        // constexpr U
using ld = long double;         // constexpr 0.0L
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define endl '\n'
#define inf 0x3f3f3f3f
#define xx first
#define yy second
#define lowbit(x) x & -x
const int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
const ll linf = 1e18;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
void solved()
{int n;cin >> n;vector<ll> a(n + 1);for (int i = 1; i <= n; i++){cin >> a[i];}ll mx=-linf,mx2=-linf,mn1=linf;ll ans = 0;for(int i=1;i<=n;i++){if(i%2){ans += a[i];mn1 = min(mn1, 2 * a[i] + i);mx = max(mx, mx2 - 2 * a[i] + i);}else{ans -= a[i];mx2=max(mx2,2*a[i]-i);mx = max(mx, 2 * a[i] + i - mn1);}}if(n%2)mx=max(mx,(ll)n-1LL);else mx=max(mx,(ll)n-2);ans+=mx;cout << ans << endl;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int T = 1;cin >> T;while (T--){solved();}return 0;
}