ChatGPT 题解

1. 题意整理

一共有个学期，每学期必须选一门课：

选 A 类课，收益是
选 B 类课，收益是

限制条件有两个：

A 类课总共最多选次
B 类课连续选的学期数不能超过

求最大总收益，如果无论如何都无法满足条件，就输出。

2. 为什么适合动态规划

每个学期都只有两种选择，而且限制条件和“已经选了多少次 A”以及“当前连续选了多少次 B”有关。

这正是动态规划最擅长处理的情况。

3. 状态设计

设

表示：

已经考虑完前个学期
一共选了次 A 类课
当前连续选了次 B 类课

时，能够获得的最大收益。

如果这个状态根本不可能到达，就记为一个很小的数，比如。

4. 状态转移

假设现在在状态，说明前个学期已经处理完了。

接下来处理第个学期：

选择 A 类课

A 类课总次数加
连续 B 的次数清零
收益加上

所以可以转移到：

选择 B 类课

A 类课次数不变
连续 B 的次数加
只要新的连续 B 次数不超过
收益加上

所以可以转移到：

5. 初始状态和答案

初始时还没有选任何课：

其他状态都不可达。

最后答案就是：

如果这个最大值仍然是负无穷，说明根本不存在合法方案，输出。

6. 为什么这样一定正确？

因为每个学期的决策只影响两个东西：

A 类课总共用了多少次
当前 B 类课连续了多少次

而这两个量已经完整地写进了状态里，所以不会丢失信息。

动态规划枚举了所有合法决策，并且每一步都保留当前最优值，因此最后得到的一定是全局最优解。

7. 复杂度分析

状态总数是。

每个状态只会转移两次，所以总复杂度是：

题目里，这个复杂度完全没问题。

8. 参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, K;
    cin >> N >> M >> K;

    vector<long long> A(N + 1), B(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
    }
    for (int i = 1; i <= N; ++i) {
        cin >> B[i];
    }

    const long long NEG = -(1LL << 60);
    static long long dp[81][81][81];

    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j <= M; ++j) {
            for (int k = 0; k <= K; ++k) {
                dp[i][j][k] = NEG;
            }
        }
    }

    dp[0][0][0] = 0;

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= M; ++j) {
            for (int k = 0; k <= K; ++k) {
                if (dp[i][j][k] == NEG) {
                    continue;
                }

                if (j < M) {
                    dp[i + 1][j + 1][0] = max(dp[i + 1][j + 1][0], dp[i][j][k] + A[i + 1]);
                }

                if (k < K) {
                    dp[i + 1][j][k + 1] = max(dp[i + 1][j][k + 1], dp[i][j][k] + B[i + 1]);
                }
            }
        }
    }

    long long ans = NEG;
    for (int j = 0; j <= M; ++j) {
        for (int k = 0; k <= K; ++k) {
            ans = max(ans, dp[N][j][k]);
        }
    }

    if (ans == NEG) {
        cout << -1 << '\n';
    } else {
        cout << ans << '\n';
    }

    return 0;
}