休息时间

AcWing-288-休息时间

分析

见《进阶指南》第295页。

实现

#include <iostream>
#include <cstring>
#define inf 0x3f3f3f3f
using namespace std;

const int N = 3840;
int n, u[N], b;
int f[2][N][2];

int main () {
    cin >> n >> b;
    for (int i = 1; i <= n; ++ i) cin >> u[i];

    
    memset(f, -0x3f, sizeof(f));
    f[1][0][0] = f[1][1][1] = 0;
    for (int i = 2; i <= n; ++ i) {
        for (int j = 0; j <= b; ++ j) {
            f[i & 1][j][0] = max(f[(i - 1) & 1][j][0], f[(i - 1) & 1][j][1]);
            f[i & 1][j][1] = -inf;
            if (j != 0) {
                f[i & 1][j][1] = max(
                    f[(i - 1) & 1][j - 1][0],
                    f[(i - 1) & 1][j - 1][1] + u[i]
                );
            }
        }
    }
    int res = f[n & 1][b][0];
    memset(f, -0x3f, sizeof(f));
    f[1][0][0] = 0, f[1][1][1] = u[1];
    for (int i = 2; i <= n; ++ i) {
        for (int j = 0; j <= b; ++ j) {
            f[i & 1][j][0] = max(f[(i - 1) & 1][j][0], f[(i - 1) & 1][j][1]);
            f[i & 1][j][1] = -inf;
            if (j != 0) {
                f[i & 1][j][1] = max(
                    f[(i - 1) & 1][j - 1][0],
                    f[(i - 1) & 1][j - 1][1] + u[i]
                );
            }
        }
    }
    res = max(res, f[n & 1][b][1]);
    cout << res << endl;
    return 0;
}