(慣れていないので多少雑なところもあるかもしれませんが、どうかよろしくお願いします。)

頂点 \(i,i+1\) を結ぶ辺を外辺 \(i\) と呼び、頂点 \(0,i\) を結ぶ辺を内辺 \(i\) と呼ぶことにします。ただし、内辺 \(1\) を内辺 \(N+1\) と呼ぶことがあります。

まず、内辺 \(1\) は残すものとして解きます。ここで、次の \(dp\) を考えます。

• \(dp[i]:=\) 外辺 \(1,\ldots,i-1\) および内辺 \(1,\ldots,i\) のみを考え、内辺 \(i\) を残すとき、削除する辺の重みの総和の最小値

このとき、答えは \(dp[N+1]\) となります。

これを計算する方法を考えます。明らかに \(dp[1]=0\) です。 \(i=2,\ldots,N\) に対して \(dp[i]\) を計算する際に、内辺 \(1,\ldots,N-1\) のうち最後に残した辺を \(k\) とすると、最適解において \(k\ge i-3\) が成り立ちます。

(証明) \(k<i-3\) が最適解でないことを示します。このとき、以下のいずれかが成り立ちます。

• 外辺 \(k,\ldots,i-3\) のうちいずれかは削除されている。
• 外辺 \(k+2,\ldots,i-1\) のうちいずれかは削除されている。

前者の場合を考えます。外辺 \(i-2,i-1\) の両方が残されている場合、パス \(0\to i\to i-1\to i-2\) が存在するため、二部グラフにおいて頂点 \(0,i-2\) は違う色で塗られます。よって、内辺 \(i-2\) を残せます。外辺 \(i-2,i-1\) の両方が残されていない場合、頂点 \(0,i-2\) は連結でないので、内辺 \(i-2\) を残すことができます。後者の場合も同様に内辺 \(k+2\) を残せます。(証明終わり)

よって、計算式は次のようになります。 \(dp[i]=\min(dp[i-1]+B_{i-1},dp[i-2]+A_{i-1},dp[i-3]+A_{i-2}+A_{i-1}+\min(B_{i-1},B_{i-2},B_{i-3}))\)

また、この議論より、内辺 \(1,2,3\) のうちどれか \(1\) つは残されることがわかります。

よってこれらについて上の \(dp\) を \(3\) 回行うことで \(O(N)\) で答えが求まります。

実装例 (Python)

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
def solve(i):
    dp = [0]*(N+1)
    for j in range(N):
        dp[j+1] = dp[j] + B[(i+j)%N]
        if j:
            dp[j+1] = min(dp[j+1], dp[j-1] + A[(i+j)%N])
        if j > 1:
            dp[j+1] = min(dp[j+1], dp[j-2] + A[(i+j)%N] + A[(i+j-1)%N] + min(B[(i+j)%N], B[(i+j-1)%N], B[(i+j-2)%N]))
    return dp[N]
ans = min(solve(0), solve(1), solve(2))
print(ans)