冲浪：最大快乐值算法 - 动态规划解题 - 常规

冲浪问题：最大快乐值

冲浪大师睿睿打算冲浪 'n' 分钟，每分钟内他可以选择一朵浪花冲上去站 '1' 分钟，站满 '1' 分钟后，这朵浪花就会消散于大海中，睿睿需要换一朵浪花，否则他就会掉进海里。

最开始有 'm' 朵浪花，就算睿睿不站上去，浪花会在某个时刻自然消散，第 'i' 朵浪花会在第 'a_i' 分钟结束时消散。每朵浪花能带给睿睿的快乐是不同的，站在第 'i' 朵浪花上会给睿睿带来 'b_i' 的快乐。

如果睿睿掉进了海里，那么他之前获得的快乐都会消失，他需要从 '0' 开始重新积累快乐。

求睿睿 'n' 分钟结束时的最大快乐值。

输入格式

从标准输入读入数据。第一行输入两个正整数 'n'（'n ≤ 500'）和 'm'（'m ≤ 2000'）。第二行输入 'm' 个正整数 'a_i'（'a_i ≤ n'）。第三行输入 'm' 个正整数 'b_i'（'b_i ≤ 1000'）。

输出格式

输出到标准输出。输出一个整数，表示最大快乐值。

样例 #1

样例输入 #1

6 8
4 2 6 2 6 1 1 6
13 14 5 7 4 3 8 1

样例输出 #1

提示

样例1解释

一种最优的浪花安排为（浪花的格式为 '(a_i,b_i)'）： '(1,8),(2,14),(6,1),(4,13),(6,4),(6,5)'

代码实现（C++）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(m);
    vector<int> b(m);
    for (int i = 0; i < m; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> b[i];
    }
    
    vector<int> dp(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i - 1]; // 不站上浪花
        for (int j = 0; j < m; j++) {
            if (i >= a[j]) {
                dp[i] = max(dp[i], dp[i - a[j]] + b[j]);
            }
        }
    }
    
    cout << dp[n] << endl;
    
    return 0;
}

代码解释：

dp[i] 表示在第 'i' 分钟结束时，睿睿可以获得的最大快乐值。
dp[i - 1] 表示在第 'i - 1' 分钟结束时，睿睿可以获得的最大快乐值，也就是选择不站上任何浪花的情况。
dp[i - a[j]] + b[j] 表示选择站在第 'j' 朵浪花上，并且在第 'i - a[j]' 分钟结束时，睿睿可以获得的最大快乐值加上站在第 'j' 朵浪花上获得的快乐值。
max(dp[i], dp[i - a[j]] + b[j]) 通过比较，选择不站上浪花和站上浪花两种情况下的最大快乐值。

最终，dp[n] 表示在第 'n' 分钟结束时，睿睿可以获得的最大快乐值。

总结：

本题通过动态规划算法，将问题分解为多个子问题，并利用子问题的解来推导出最终的解。代码简洁易懂，逻辑清晰，体现了动态规划算法的优势。