$O(N)$ DP

动物排列成环，每种喂食方式覆盖相邻的两只动物，花费为给定的数组 $A$ 中的值。目标是用最小花费选择一组喂食方式，使得每只动物至少被覆盖一次。

关键思路：将环形问题拆解为两个线性问题：

情况1：不使用连接动物 $N$ 和动物 $1$ 的边（最后一条边）。此时，问题转化为线性链（动物 $1$ 到动物 $N$ ）。使用动态规划求解覆盖链的最小花费。

情况2：使用连接动物 $N$ 和动物 $1$ 的边。此时，动物 $1$ 和动物 $N$ 已被覆盖，问题转化为覆盖动物 $2$ 到动物 $N-1$ 的线性链。同样使用动态规划求解，最后加上最后一条边的花费。

动态规划：

情况 $1$ 的DP：定义 $dp[N][2]$ ，$dp[i][0]$ 和 $dp[i][1]$ 分别表示不选择当前边和选择当前边时的最小花费。状态转移方程为：

• dp[i][0] = dp[i - 1][1]（不使用当前边，则前一条边必须被使用）

• dp[i][1] = min(dp[i - 1][1], dp[i - 1][0]) + a[i]（使用当前边，则前一条边可选可不选）

情况 $2$ 的DP：与情况 $1$ 类似，但初始状态和范围不同。最后取选择最后一条边的状态，加上最后一条边的花费。

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<LL, LL> PII;

#define x first
#define y second

const int N = 3e5 + 10, mod = 998244353;

int n;
int a[N];
LL f1[N][2], f2[N][2];

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    
    f1[1][0] = 1e18;
    f1[1][1] = a[1];
    for(int i = 2; i <= n; i ++)
    {
        f1[i][0] = f1[i - 1][1];
        f1[i][1] = min(f1[i - 1][1], f1[i - 1][0]) + a[i];
    }
    
    f2[0][0] = 1e18;
    f2[0][1] = a[n];
    for(int i = 1; i < n; i ++)
    {
        f2[i][0] = f2[i - 1][1];
        f2[i][1] = min(f2[i - 1][1], f2[i - 1][0]) + a[i];
    }
    cout << min({f1[n][1], f1[n][0], f2[n - 1][1], f2[n - 1][0]}) << endl;
}

int main()
{
    int t = 1;
    // cin >> t;
    while(t --)
        solve();
}