#AT17. Flowers
Flowers
[Q] Flowers(dp_q)
来源: AtCoder Educational DP Contest - Problem Q 原题时限:2 秒 / 内存:1024 MB
题目描述
有 朵花排成一排。对于每个 (),从左数第 朵花的高度为 ,美丽值为 。保证 两两不同。
太郎要拔掉一些花,使得剩下的花满足:
- 剩下的花从左到右高度单调递增。
求剩下花的美丽值之和的最大可能值。
输入格式
输入由标准输入按以下格式给出:
N
h_1 h_2 \ldots h_N
a_1 a_2 \ldots a_N
输出格式
输出剩下花的美丽值之和的最大值。
数据范围
- 输入中的所有值均为整数。
- 两两不同。
样例 1
输入:
4
3 1 4 2
10 20 30 40
输出:
60
样例 2
输入:
1
1
10
输出:
10
样例 3
输入:
5
1 2 3 4 5
1000000000 1000000000 1000000000 1000000000 1000000000
输出:
5000000000
样例 4
输入:
9
4 2 5 8 3 6 1 7 9
6 8 8 4 6 3 5 7 5
输出:
31