要不然呢
by piggy123 @ 2022-05-14 21:57:20
$dp[i][0/1]$ 第 $i$ 个选不选
```cpp
#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize("-Ofast")
using namespace std;
const int NR = 3e6 + 5;
int n, ans = 1e18, a[NR], f[NR][2];
signed main() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
memset(f, 0x3f, sizeof(f));
f[1][1] = a[1];
for (int i = 2; i <= n; ++i) {
f[i][1] = min(f[i - 1][0], f[i - 1][1]) + a[i];
f[i][0] = f[i - 1][1];
}
ans = min(ans, min(f[n][1], f[n][0]));
memset(f, 0x3f, sizeof(f));
f[1][0] = 0;
for (int i = 2; i <= n; ++i) {
f[i][1] = min(f[i - 1][0], f[i - 1][1]) + a[i];
f[i][0] = f[i - 1][1];
}
ans = min(ans, f[n][1]);
cout << ans << endl;
return 0;
}
```
by rsg23 @ 2022-05-14 21:57:26
同求，一直 AC17 WA9，吃了 6 发罚时/fn/fn
by Kobe303 @ 2022-05-14 21:57:35
就是 DP，简单的环形 DP
by cancan123456 @ 2022-05-14 21:57:35
@[GIAOchen](/user/431658) E 的确是 dp。设 $f_{i,0}$ 表示不选第 $i$ 个时的最小值，$f_{i,1}$ 表示选第 $i$ 个时的最小值，则容易推出 $f_{i,0}=f_{i-1,1},f_{i,1}=\min\{f_{i-1,1},f_{i-1,0}\}+a_i$。
注意要考虑边界问题，并且因为第 $n$ 个数和第 $1$ 个数可能重复，要算以第 $n$ 个和第 $1$ 个开头两种情况。
~~我被这个问题卡了大概 10min~~
by donghanwen1225 @ 2022-05-14 21:58:56
@[UnAccepting自动机](/user/448887) 我就是左右端点（$1$ 和 $n$ ）的边界没搞好
by LaDeX @ 2022-05-14 21:59:54
无语
by LaDeX @ 2022-05-14 22:00:06
这难道不是环形 DP 基本套路吗？
by cancan123456 @ 2022-05-14 22:06:54