頂点 \(0,1,\ldots,N\) の順に頂点を赤青に塗り分けて、同色の頂点を結ぶ辺の重みを足すことを考えましょう。

頂点 \(0\) は赤色として一般性を失いません。

ここで、一旦頂点 \(1\) と頂点 \(N\) を結ぶ辺のみ無視したうえで、次の \(dp\) を考えます。

\(dp[i][j][k] :=\) 頂点 \(i\) まで色を塗り終わった時の辺の重みの和の最小値

ただし、頂点 \(i\) の色は \(j\) で、頂点 \(1\) の色は \(k\) である。( \(j\) と \(k\) は、\(0\) を赤色、\(1\) を青色とする)

\(dp[i]\) は \(dp[i-1]\) から求めることができます。(遷移や初期値が分からなければ下の実装例も参考にしてください。)

最後に、\(dp[N]\) の値に、頂点 \(1\) と頂点 \(N\) を結ぶ辺も考慮すれば答えを出すことができます。

計算量は \(O(N)\) です。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
void chmin(ll &a,ll b){a = min(a,b);}
ll inf = 1e18;

signed main(){
    ll n;cin>>n;
    vector<ll> a(n+1),b(n+1);
    rep(i,1,n)cin>>a[i];
    rep(i,1,n)cin>>b[i];
    vector<vector<vector<ll>>> dp(n+1,vector<vector<ll>>(2,vector<ll>(2,inf)));
    dp[1][0][0] = a[1];
    dp[1][1][1] = 0;
    rep(i,2,n)rep(j,0,1)rep(k,0,1)rep(prej,0,1){
        chmin(dp[i][j][k],dp[i-1][prej][k] + (j==0?a[i]:0) + (j==prej?b[i-1]:0));
    }
    ll ans = inf;
    rep(j,0,1)rep(k,0,1)chmin(ans,dp[n][j][k] + (j==k?b[n]:0));
    cout<<ans<<endl;
    return 0;
}