冲浪：最大快乐值动态规划算法

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

提示

样例1解释

一种最优的浪花安排为（浪花的格式为 (a_i, b_i)）：

(1, 8), (2, 14), (6, 1), (4, 13), (6, 4), (6, 5)

C++ 代码示例cpp#include #include #include using namespace std;

int main() { int n, m; cin >> n >> m; vector a(m), 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); 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;