DP环形结构两种处理方法(两次DP(一次断开,一次强制连接), 环拆成链复制一倍)

 AcWing 288. 休息时间(两次DP + 滚动数组优化)

//F[i, j, 0&1]表示当前i个时间段时,一共选了j个,并且当前的选(1)或者不选(0)时获得的恢复值的最大值
//F[i, j, 1] = max(F[i - 1, j - 1, 1] + U[i], F[i - 1][j - 1][0])
//F[i, j, 0] = max(F[i - 1, j, 1], F[i - 1, j, 0])
//直接存储可能会爆空间,所以我们采用滚动数组优化
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3840;
int n, m;
int F[2][N][2], a[N];
signed main(){cin >> n >> m;for (int i = 1; i <= n; ++i)cin >> a[i];//当第n个小时睡觉时memset(F, 0xcf, sizeof F);F[1][0][0] = 0, F[1][1][1] = a[1];for (int i = 2; i <= n; ++i)for (int j = 0; j <= min(i, m); ++j){if (j >= 1)F[i & 1][j][1] = max(F[(i - 1) & 1][j - 1][1] + a[i], F[(i - 1) & 1][j - 1][0]);F[i & 1][j][0] = max(F[(i - 1) & 1][j][1], F[(i - 1) & 1][j][0]);}int ans = F[n & 1][m][1];//当第n个小时不睡觉时memset(F, 0xcf, sizeof F);F[1][0][0] = F[1][1][1] = 0;for (int i = 2; i <= n; ++i)for (int j = 0; j <= min(i, m); ++j){if (j >= 1)F[i & 1][j][1] = max(F[(i - 1) & 1][j - 1][1] + a[i], F[(i - 1) & 1][j - 1][0]);F[i & 1][j][0] = max(F[(i - 1) & 1][j][1], F[(i - 1) & 1][j][0]);}ans = max(ans, F[n & 1][m][0]);cout << ans << '\n';
}