F - Select Half

题意

$n$n个数里选 $\lfloor \frac{n}{2}\rfloor$⌊2n​⌋个数，求最大值为多少？

思路

我想不到下面的DP是因为我菜，我刷的DP题太少了，那就多刷一点就能想到了。
DP
令 $f\left[i\right]$f[i]表示 $i$i个数里选 $\lfloor \frac{i}{2}\rfloor$⌊2i​⌋里最大的数为多少。
预处理 $sum\left[i\right]$sum[i]表示隔一个取一个到第 $i$i个位置（包含 $i$i）的和为多少。
$i$i为奇 $:f\left[i\right]=max\left(f\right[i-2]+a[i],f[i-1\left]\right)$:f[i]=max(f[i−2]+a[i],f[i−1])
$i$i为偶 $:f\left[i\right]=max\left(f\right[i-2]+a[i],sum[i-1\left]\right)$:f[i]=max(f[i−2]+a[i],sum[i−1])
注意 $：$：因为是下取整，所以 $i$i从 $2$2开始取第一个数，故 $DP$DP要从 $2$2开始。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 2e5 + 5;

ll n,a[N],f[N],sum[N];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=(i>1?sum[i-2]:0)+a[i];
	}
	for(int i=2;i<=n;i++){
		if(i&1) f[i]=max(f[i-2]+a[i],f[i-1]);
		else f[i]=max(f[i-2]+a[i],sum[i-1]);
	}
	cout<<f[n]<<'\n';
	return 0;
}