冲浪

题目描述

冲浪大师睿睿打算冲浪 '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 84 2 6 2 6 1 1 613 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)'

这是代码：cpp#include #include #include using namespace std;

int main() { int n, m; cin >> n >> m; vector a(m); vector b(m); for (int i = 0; i < m; i++) { cin >> a[i]; } for (int i = 0; i < m; i++) { cin >> b[i]; } vector 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]); } } for (int j = 0; j < m; j++) { if (i >= a[j]) { dp[i] = max(dp[i], dp[i - 1] + b[j]); } } } cout << dp[n] << endl; return 0;}

这样修改后，代码会正确计算最大快乐值。