题目详情题解（0）讨论（0）提交记录（0）

AT_dp_x.Tower

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

你有 nn 个箱子，编号从 11 到 nn，每个箱子有三个属性，以第 ii 个箱子为例，分别是重量 wiw_i，承重能力 sis_i，价值 viv_i。

你想建一座塔，因此需要将一些箱子堆叠起来，但是每个箱子必须满足下面的条件：

  • 这个箱子上面的所有箱子重量和要小于等于这个箱子的承重能力。

定义一个塔的价值为它所用的所有箱子的价值和。

最大化这个塔的价值并输出它。

输入格式

第一行一个整数 nn，表示箱子数量。

接下来 nn 行，一行三个整数，用来描述这个箱子的三个属性 wi,si,viw_i,s_i,v_i。

输出格式

一行一个整数，表示塔的最大价值。

输入输出样例

  • 输入#1

    3
2 2 20
2 1 30
3 1 40

    输出#1

    50

  • 输入#2

    4
1 2 10
3 1 10
2 4 10
1 6 10

    输出#2

    40

  • 输入#3

    5
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000

    输出#3

    5000000000

  • 输入#4

    8
9 5 7
6 2 7
5 7 3
7 8 8
1 9 6
3 3 3
4 1 7
4 5 5

    输出#4

    22

说明/提示

n≤103,1≤wi,si≤104,1≤vi≤109n \le 10^3, 1 \le w_i, s_i \le 10^4, 1 \le v_i \le 10^9。

输入解题思路，AI测评打分。不知道怎么写?

首页