Codeforces Round #672 (Div. 2) C1. Pokémon Army (easy version)（dp）

题意：t组输入，给n个数字，构造一个序列$a_i?a_{i+1}+a_{i+2}?...a_{i+n}$,问怎么样才能使序列值最大
题解：一道dp题目，设$dp1[]$代表序列为奇数时,$dp2[]$代表序列为偶数时，那么有

$dp1[i]=max(dp1[i?1],dp2[i?1]+a[i])$
$dp2[i]=max(dp2[i?1],dp1[i?1]?a[i]);$

最后输出最大值即可

代码：

#include<bits/stdc++.h>#pragma GCC optimize(2)
#define rep(i,a,n) for (int i=a;i<=n;i++)//i为循环变量，a为初始值，n为界限值，递增
#define per(i,a,n) for (int i=a;i>=n;i--)//i为循环变量， a为初始值，n为界限值，递减。using namespace std;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0)
#define ll long long
#define ull unsigned long long
#define ld long double
const int INF = 0x3f3f3f3f;
const ll LINF = 1ll<<60;
const int mod=1e9+7;ll read()//快读
{
    ll w = 1, s = 0;char ch = getchar();while (ch < '0' || ch>'9') {
     if (ch == '-') w = -1; ch = getchar(); }while (ch >= '0' && ch <= '9') {
     s = s * 10 + ch - '0';    ch = getchar(); }return s * w;
}
ll dp1[300010],dp2[300010];//1为奇数，2为偶数
ll n,k,a[300010];
void solve(){
    cin>>n>>k;rep(i,1,n) cin>>a[i];memset(dp1,0,sizeof(dp1));memset(dp2,0,sizeof(dp2));rep(i,1,n){
    dp1[i]=max(dp1[i-1],dp2[i-1]+a[i]);dp2[i]=max(dp2[i-1],dp1[i-1]-a[i]);}cout<<max(dp1[n],dp2[n])<<endl;
}int main(){
    int _;cin>>_;while(_--){
    solve();}return 0;
}