题目链接：https://codeforces.com/problemset/problem/1373/D
简单题意：给定一个序列，翻转一个区间至多一次，求偶数位置上的数和的最大值
注意到翻转长度为奇数的区间是无效的。如果翻转偶数长度区间，因为只考虑和，所以不用考虑整个区间，而是连续的长度为2的区间的翻转。这样对于每个长度为2的区间，算出翻转后对答案的改变值（分从下标0和下标1两种情况考虑），之后求最大子段和即可
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 5 const int maxn=2000+10; 6 int t,n,i,j,a[maxn]; 7 ll ans,b[maxn],f[maxn],sum; 8 9 void dp(int k){ 10 if (k>=n-1) return; 11 int i=k;int cnt=-1; 12 while (i<n-1){ 13 b[++cnt]=(k==0)?a[i+1]-a[i]:a[i]-a[i+1]; 14 i+=2; 15 } 16 f[0]=b[0];ll mmax=b[0]; 17 for (int i=1;i<=cnt;i++) { 18 f[i]=max(f[i-1]+b[i],b[i]); 19 mmax=max(mmax,f[i]); 20 } 21 if (mmax>0) ans=max(ans,sum+mmax); 22 } 23 24 int main(){ 25 scanf("%d",&t); 26 while (t--){ 27 scanf("%d",&n); 28 sum=0; 29 for (i=0;i<n;i++){ 30 scanf("%d",&a[i]); 31 if (i%2==0) sum+=a[i]; 32 } 33 ans=sum; 34 dp(0);dp(1); 35 cout<<ans<<endl; 36 } 37 //system("pause"); 38 return 0; 39 }
原文：https://www.cnblogs.com/edmunds/p/13216527.html
