题目大意

​ 给定一个长度为 nn 序列 a0,a1,…,an−1a0,a1,…,an−1 ，你可以翻转它的一个连续子段(可以为空) , 使得所有偶数下标的数字之和最大。

分析

​ 考虑相邻两项对答案 resres 的贡献

​ 考虑每一个偶位置 $ i $

​ 则对 res 的贡献 为 $ a[i+1] - a[i]$

​ 求一个最大连续子序列和即可

​ 当 nn 为奇数的时候考虑 a0 && an−1a_0 \ \&\& \ a_{n-1}，取哪个最大

​ 即 $ a[i-1] - a[i] $ 的最大连续子序列和与上式子的取 $ max $

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int n;
int cal(vector<int> & x){
    int res = 0;
    int ans = 0;
    for(auto i:x){
        if(res < 0) res = i;
        else res += i;
        ans = max(ans,res);
    }
    return ans;
}

signed main()
{
    cin>>n;
    vector<int> a(n+2);
    int res = 0;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        if(i&1) res += a[i];
    }

    vector<int> d1,d2;
    for(int i = 1;i < n;i+=2) d1.push_back(a[i+1] - a[i]);
    for(int i = 3;i <= n;i+=2) d2.push_back(a[i-1] - a[i]);

    cout << res + max(cal(d1),cal(d2)) << endl; 
    return 0;
}