最优的方案应该是先往一个方向走，然后走回来，再往另一个方向走不回来。考虑用 dp 模拟这个过程。设 \(f_{i,0/1}\) 表示从第 \(i\) 个点出发往左走，不一定/一定回到 \(i\) 号点的最大次数，则有转移：
\[\begin{array}{l}
f_{i,1}=f_{i-1,1}+a_{i-1}-[2 \nmid a_{i-1}]\\f_{i,0}=\max\left\{
\begin{array}{l}
f_{i-1,0}+a_{i-1}-[2 \mid a_{i-1}]\\
f_{i-1,1}+a_{i-1}\\
f_{i,1}\\
\end{array}
\right.
\end{array}
\]
转移的意义分别是：
- 从 \(i\) 出发，把 \(i-1\) 左边走完以后，不停在 \(i-1\) 和 \(i\) 之间移动，最终在 \(i\) 结束。
- 从 \(i\) 出发，先在 \(i-1\) 和 \(i\) 之间移动，最终到 \(i-1\)，走 \(i-1\) 左边的点。
- 从 \(i\) 出发，把 \(i-1\) 左边走完以后，不停在 \(i-1\) 和 \(i\) 之间移动，最终在两者任意一个结束。
- 可以回到 \(i\)。
同理维护出向右走的最大次数。时间复杂度 \(O(n)\)。
#include<iostream>
#include<cstdio>
#define int long long
#define N 100010
using namespace std;
int n,a[N],f[N][2],g[N][2],ans;
signed main(){cin>>n;for(int i=1;i<n;i++)cin>>a[i];for(int i=2;i<=n;i++){if(a[i-1]>1)f[i][1]=f[i-1][1]+a[i-1]/2*2;f[i][0]=max(f[i][1],max(f[i-1][0]+a[i-1]-(a[i-1]%2^1),f[i-1][1]+a[i-1]));}for(int i=n-1;i>=1;i--){if(a[i]>1)g[i][1]=g[i+1][1]+a[i]/2*2;g[i][0]=max(g[i][1],max(g[i+1][0]+a[i]-(a[i]%2^1),g[i+1][1]+a[i]));}for(int i=1;i<=n;i++){ans=max(ans,f[i][0]+g[i][1]);ans=max(ans,f[i][1]+g[i][0]);}cout<<ans;return 0;
}