Educational Codeforces Round 90 (Rated for Div. 2)   参与排名人数12840

[codeforces 1373D]    Maximum Sum on Even Positions  翻转不改变相对位置+两种交换形式

总目录详见https://blog.csdn.net/mrcrack/article/details/103564004

在线测评地址http://codeforces.com/contest/1373/problem/D

题目大意：给定一个数组，可以至多对其中的连续子序列进行一次翻转，求出所有可能中的，该数组偶数位置上的元素最大和。

样例模拟如下

8
1 7 3 4 7 6 2 926位置0 1 2 3 4 5 6 7
数值1 7 3 4 7 6 2 9
翻转后位置区间[0,7]对应的元素翻转后
位置0 1 2 3 4 5 6 7
数值9 2 6 7 4 3 7 1偶数位上元素和9+6+4+7=265
1 2 1 2 15位置0 1 2 3 4
数值1 2 1 2 1
翻转后位置区间[0,3]对应的元素翻转后
位置0 1 2 3 4
数值2 1 2 1 1 偶数位上元素和2+2+1=510
7 8 4 5 7 6 8 9 7 337位置0 1 2 3 4 5 6 7 8 9
数值7 8 4 5 7 6 8 9 7 3
翻转后位置区间[1,2]对应的元素翻转后
位置0 1 2 3 4 5 6 7 8 9
数值7 4 8 5 7 6 8 9 7 3偶数位上元素和7+8+7+8+7=374
3 1 2 15位置0 1 2 3
数值3 1 2 1偶数位上元素和3+2=5

可以看到，翻转不改变元素间相对位置。

如位置0 1 2 3 4,位置1可与位置0交换,也可与位置2交换，需要讨论两种交换形式。

交换后，偶数位和值，只需在原理基础上，补上差值即可。

AC代码如下：

#include <cstdio>
#include <algorithm>
#define LL long long
#define maxn 200010
using namespace std;
int a[maxn];
LL sum;
int main(){int t,i,n;LL cur,delta1,delta2,delta;scanf("%d",&t);while(t--){scanf("%d",&n);for(i=0;i<n;i++)scanf("%d",&a[i]);sum=0;for(i=0;i<n;i+=2)sum+=a[i];cur=0,delta1=0;for(i=1;i<n;i+=2){//位置0与位置1交换cur+=a[i]-a[i-1];//cur用来计算连续区间内，交换后的差值delta1=max(delta1,cur);if(cur<0)cur=0;//重新开始新的区间}cur=0,delta2=0;for(i=2;i<n;i+=2){//位置2与位置1交换cur+=a[i-1]-a[i];delta2=max(delta2,cur);if(cur<0)cur=0;//重新开始新的区间}delta=max(delta1,delta2);sum+=delta;printf("%lld\n",sum);}return 0;
}