传送门

题目:给定长度为n的数组,下标从0开始。你可以至多翻转一次连续的子数组,问a0 + a2 + ... + a2k最大是多少。

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

思路:我们发现一个情况: 20 30 10 ...,我们发现如果30和20反转也可以和后面10的的反转,就分成了两种情况,我们可以通过dp来解决,当前这个数与左边一起反转差值还是与右边一起反转翻转差值大。

初始化dp[0~n] = 0,我们把下标改成从1开始,则变成a1 + a3 + a5 + ... + a2k-1。

①i & 1 : dp[i] = max(dp[i], dp[i - 2] + a[i - 1] - a[i]

②!(i&1): dp[i] = max(dp[i], dp[i - 2] + a[i] - a[i - 1)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <queue>
 5 #include <string>
 6 #include <vector>
 7 #include <cmath>
 8  
 9 using namespace std;
10  
11 #define ll long long
12 #define pb push_back
13 #define fi first
14 #define se second
15  
16 const int N = 2e5 + 10;
17 ll a[N], dp[N], sum; 
18 
19 void solve()
20 {      
21     int T;
22     cin >> T;
23     while(T--){
24         int n;
25         cin >> n;
26 
27         sum = 0;
28         for(int i = 1; i <= n; ++i){
29             cin >> a[i];
30             if(i & 1) sum += a[i];
31         }
32         for(int i = 1; i <= n; ++i) dp[i] = 0;
33 
34         for(int i = 2; i <= n; ++i){
35             if(i & 1){
36                 dp[i] = max(dp[i], dp[i - 2] + a[i - 1] - a[i]);
37             }else{
38                 dp[i] = max(dp[i], dp[i - 2] + a[i] - a[i - 1]);
39             }
40         }
41 
42         ll max_d = 0;
43         for(int i = 0; i <= n; ++i) max_d = max(max_d, dp[i]);
44         //cout << "max = ";
45         cout << sum + max_d << endl;    
46     }
47 }
48  
49 int main()
50 {
51     ios::sync_with_stdio(false);
52     cin.tie(0);
53     cout.tie(0); 
54     solve();
55  
56     return 0;
57 }

 

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄