Codeforce 1420 C1. Pokémon Army (easy version) 解析(DP)

今天我們來看看CF1420C1
題目連結

題目
對於一個數列$a$，選若干個數字，求alternating-series的最大值。

前言

C2真的想不到

想法

$dp[i][0]$代表:考慮到第i個數字為止，最後一個數字是負的的最大值
$dp[i][1]$代表:考慮到第i個數字為止，最後一個數字是正的的最大值
$dp[i][0]=max{dp[i-1][0],dp[i-1][1]-a[i]}$
$dp[i][1]=max{dp[i-1][1],dp[i-1][0]+a[i],a[i]}$
記得令$dp[0][0]$為極小值，且答案要開$long\ long$
答案是$max{dp[n-1][0],dp[n-1][1])}$

程式碼:

const int _n=3e5+10;  
int t,n,q,a[_n],l,r,dp[_n][2];  
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  cin>>t;while(t--){  
    cin>>n>>q;rep(i,0,n)cin>>a[i];ll ans=0;  
    rep(i,0,n)dp[i][0]=dp[i][1]=0;  
    dp[0][0]=-1e5,dp[0][1]=a[0];  
    rep(i,1,n){  
      dp[i][0]=max(dp[i-1][0],dp[i-1][1]-a[i]);  
      dp[i][1]=max(dp[i-1][1],max(dp[i-1][0]+a[i],a[i]));  
    }cout<<max(dp[n-1][0],dp[n-1][1])<<'\n';  
  }  
  return 0;  
}  

標頭、模板請點Submission看
Submission