「poj 2228」Naptime (环形DP)

poj 2228
题意：有一个环，选择一段长度为$n$进行计算。如果第i个时间点选择不睡觉那么就会增加$a_i$。你也可以选择睡觉，第一个时间点不算，睡觉时间至少为$m$。

先考虑线性做法，设$dp(i,j,0/1)$为前$i$个选了$j$个睡觉，$i$不选/选的最大值。
转移显然
$$
\begin{cases}
dp(i,j,0)=min(dp(i-1,j,0),dp(i-1,j,1)) \\
dp(i,j,1)=min(dp(i-1,j-1,0), dp(i-1,j-1,1)+a_i)
\end{cases}
$$
由于1位置一定不能对答案贡献，所以初值$dp(1, 0, 0)=dp(1, 1, 1)=0$，其他负无穷大
答案为$max(dp(n, b, 0), dp(n, b, 1))$
如果考虑环上做法，我们之前的做法相当于在$1$和$n$处断开了链，现在要将他强行接上去，我们可以这次强行选择$1,n$睡觉，然后再做一次DP，综合两者答案。
所以初值改为$dp(1, 0, 0)=0, dp(1, 1, 1)=a_i$，其他负无穷大
答案为$dp(n, b, 1)$
综合两者答案即可。注意要用滚动数组。

知识点：
1、环形不一定要复制两遍

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL INF = 4223372036854775808ll;

    int n, b, a[3831];
    LL dp[2][3831][2], ans;

    void clean() {
        ans = 0ll;
        for (int i = 0; i <= 1; ++i)
        for (int j = 0; j <= b; ++j) dp[i][j][0] = dp[i][j][1] = -INF;
    }
    int solve() {
        scanf("%d%d", &n, &b);
        clean();
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        int cur = 1;
        dp[1][0][0] = dp[1][1][1] = 0;
        for (int i = 2; i <= n; ++i) {
            cur ^= 1;
            for (int j = 0; j <= min(i, b); ++j) {
                dp[cur][j][0] = max(dp[cur ^ 1][j][0], dp[cur ^ 1][j][1]);
                if (j - 1 >= 0) {
                    dp[cur][j][1] = max(dp[cur ^ 1][j - 1][0], dp[cur ^ 1][j - 1][1] + (LL)a[i]);
                }
            }
        }
        ans = max(dp[cur][b][0], dp[cur][b][1]);
        for (int i = 0; i <= 1; ++i)
        for (int j = 0; j <= b; ++j) dp[i][j][0] = dp[i][j][1] = -INF;
        cur = 1;
        dp[1][0][0] = 0, dp[1][1][1] = a[1];
        for (int i = 2; i <= n; ++i) {
            cur ^= 1;
            for (int j = 0; j <= min(i, b); ++j) {
                dp[cur][j][0] = max(dp[cur ^ 1][j][0], dp[cur ^ 1][j][1]);
                if (j - 1 >= 0) {
                    dp[cur][j][1] = max(dp[cur ^ 1][j - 1][0], dp[cur ^ 1][j - 1][1] + (LL)a[i]);
                }
            }
        }
        ans = max(ans, dp[cur][b][1]);
        cout << ans;
        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}