不知道能不能用贪心,反正我是没看出来,所以用DP求解。
首先分析一下题意,我们要在一段序列中取出一段子序列,然后让这段子序列按顺序逐个先加后减最终得到的结果最大。
如果要用DP,那么我们首先就要思考怎么表示状态,并且怎么扫能够把所有情况都涵盖。
在这道题里面有两种状态,第一种是应该加的状态,也就是说我们刚刚减完,另一种是应该减的状态,这时候我们刚刚加完一个数。
那么我们就用 f [ i ] [ j ] f[i][j] f[i][j] 和 f [ i ] [ j ] f[i][j] f[i][j] 来表示从前 i i i个里面选,状态为 j j j的所有集合里面能够取到的最大值。
这里的 j j j就直接用 0 0 0和 1 1 1来表示就可以了,官方题解是将两个状态拆为了两个DP数组(感觉不太好理解)。
在这里用 0 0 0 表示上一次减完的状态, 1 1 1 表示上一次加完的状态。
那么我们很容易知道,只有在第 i − 1 i-1 i−1次处于减过了一个数的状态才能够进行加操作或者不进行操作,这时候的状态转移方程就是 f [ i ] [ 1 ] = m a x ( f [ i − 1 ] [ 1 ] , f [ i − 1 ] [ 0 ] + a [ i ] ) f[i][1] = max(f[i-1][1],f[i-1][0] +a[i]) f[i][1]=max(f[i−1][1],f[i−1][0]+a[i])
只有第i-1次加过了一个数的状态才能够进行减操作或者不进行操作,这时候的状态表示为 f [ i ] [ 0 ] = m a x ( f [ i − 1 ] [ 0 ] , f [ i − 1 ] [ 1 ] − a [ i ] ) f[i][0] = max(f[i-1][0],f[i-1][1] - a[i]) f[i][0]=max(f[i−1][0],f[i−1][1]−a[i])
CODE:
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
#define int long long
int a[N];
int f[N][2];
//1 - / 0 +
void solve(){
int n,q;cin >> n >> q;
for(int i = 1;i <= n;i++)cin >> a[i];
for(int i = 1;i <= n;i++){
f[i][1] = max(f[i-1][1],f[i-1][0] + a[i]);
f[i][0] = max(f[i-1][0],f[i-1][1] - a[i]);
}
cout << max(f[n][1],f[n][0]) << endl;
}
signed main(){
int T;cin >> T;
while(T--){
solve();
}
return 0;
}