https://codeforces.com/contest/1373/problem/D

题意：给出一个序列（从0开始计数）让我们求出偶数位置的最大和

　　　我们最多可以执行一次让某个连续区间翻转的操作；

思路：模拟一下可知，奇数个数的翻转是无效的，所以只能偶数个数的翻转

　　　我们求出相邻位置的差，记录下来，这里就有两种情况

　　　我们通过一个序列来看这两种情况 0 1 2 3 4 5 6

　　　我们可以用（0，1）（2，3）（4，5）这样子进行

　　　也可以（1，2）（3，4）（5，6）

　　　所以把这两种情况分别列举

　　　然后就会得出另外一个序列 ,求这个序列的最大子段和即可

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn=2e5+10;
 5 int b[maxn];
 6 int a[maxn];
 7 int len;
 8 ll cal(int n)
 9 {
10     ll sum,maxsum;
11     sum=maxsum=0;
12     for(int i=1;i<=n;i++){
13         sum+=1ll*a[i];
14         if(sum>maxsum) maxsum=sum;
15         else if(sum<0) sum=0;
16     }
17     return maxsum;
18 }
19 int main()
20 {
21     int T;
22     scanf("%d",&T);
23     while(T--){
24         int n;
25         scanf("%d",&n);
26         ll res=0;
27         for(int i=0;i<n;i++){
28             scanf("%d",&b[i]);
29             if(i%2==0) res+=1ll*b[i];
30         }
31         len=0;
32         for(int i=1;i<n;i+=2)
33             a[++len]=b[i]-b[i-1];
34         ll ans=cal(len);
35         len=0;
36         for(int i=2;i<n;i+=2){
37             a[++len]=b[i-1]-b[i];
38         }
39         ans=max(ans,cal(len));
40         res+=ans;
41         printf("%lld\n",res);
42     }
43     return 0;
44 }

View Code