Codeforce 1420 C1. Pokémon Army (easy version) 解析(DP)
今天我們來看看CF1420C1
題目連結
題目
對於一個數列\(a\),選若干個數字,求alternating-series的最大值。
前言
C2真的想不到
觀看更多正版原始文章請至petjelinux的blog
想法
\(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