Work or Rest

原题链接

TAG：动态规划

思路

定义 \(dp[i][j]\) 表示工作了 \(i\) 天，上一次休息在 \(j\) 天前所能获得的最大工作收益。

状态转移：

• \(dp[i+1][0]=\max(dp[i+1][0],dp[i][j]+b[j])\)
• \(dp[i+1][j+1]=\max(dp[i+1][j+1],dp[i][j])\)

其中 \(b[i]\) 表示连续工作 \(i\) 天可以获得的工作效益，\(b[d]=\sum_{i=1}^{d}a[\left\lfloor\frac{i+1}{2}\right\rfloor]\)。

定义 \(dp[1][0] = 0\)，即每个星期的第一天都是假期。

最终答案为 \(ans=\max(ans,dp[n][i]+b[i])(0\le i\le N-1)\)。

代码

#include <bits/stdc++.h>
using LL = long long;

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int n;
    std::cin >> n;
    std::vector<LL> a(n + 1), b(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        b[i] = b[i - 1] + a[(i + 1) / 2];
    }

    std::vector<std::vector<LL>> dp(n + 1, std::vector<LL>(n + 1, -4e18));
    dp[1][0] = 0;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= n; j++) {
            if (dp[i][j] < 0) continue;
            dp[i + 1][j + 1] = std::max(dp[i + 1][j + 1], dp[i][j]);
            dp[i + 1][0] = std::max(dp[i + 1][0], dp[i][j] + b[j]);
        }
    }

    LL res = 0;
    for (int i = 0; i < n; i++) {
        res = std::max(res, dp[n][i] + b[i]);
    }
    std::cout << res << "\n";

    return 0;
}