冲浪 - 最大快乐值问题

题目描述

冲浪大师睿睿打算冲浪 '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

45

提示

样例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), b(m);
    for (int i = 0; i < m; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> b[i];
    }
    
    // 构建dp数组，dp[i]表示在第i分钟结束时的最大快乐值
    vector<int> dp(n + 1, 0);
    
    // 遍历每个浪花
    for (int i = 0; i < m; i++) {
        // 遍历每个时间点
        for (int j = n; j >= a[i]; j--) {
            // 在第j分钟结束时，可以选择站在第i朵浪花上或者不站
            dp[j] = max(dp[j], dp[j - a[i]] + b[i]);
        }
    }
    
    cout << dp[n] << endl;
    
    return 0;
}