返回首页 返回题库

选数

C++ 中等 GESP六级真题 #动态规划

题目描述

题面描述

给定两个包含 个整数的数组 与 。你需要指定若干下标 ()使得以下条件成立:

  • ;
  • 。

你需要在满足以上条件的前提下最大化 ,也即最大化数组 对应下标的整数之和。

输入格式

第一行,一个正整数 ,表示数组长度。

第二行, 个整数 ,表示数组 。

第三行, 个整数 ,表示数组 。

输出格式

一行,一个整数,表示在满足下标条件的前提下,数组 对应下标的整数之和的最大值。

样例1

输入:

4
1 2 3 4
3 3 1 1

输出:

7

样例2

输入:

6
1 1 4 5 1 4
1 2 3 2 1 0

输出:

11

数据范围

对于 的测试点,保证 。

对于所有测试点,保证 ,,。

时间限制

1.0 s

内存限制

512.0 MB

💡 查看提示(先自己想一想再看)
本题考察动态规划的线性递推优化。定义dp[i]表示处理完前i个位置时的最大收益,递推时考虑两种情况:不选第i个元素,直接继承前一个位置的最大值;选第i个元素时,更新i+b[i]位置的最大收益。最终取所有可能的选法中的最大值即可,时间复杂度为O(n),可以处理1e5的数据规模。注意a_i的范围较大,需要使用long long类型存储结果避免溢出。
⚙ 开始做这道题 0 人做过 · 0 收藏 · 5 浏览

讨论(0)