U598009 [Badcat题目合集]搭积木

小A有N个不同的积木，每个积木都有一个高度h_i和一个宽度w_i。现在他想把这些积木堆叠起来，形成一个尽可能高的塔。堆叠积木需要满足以下条件： 1. 每个积木只能使用一次，或不使用 2. 对于塔中从下往上数的第i个积木（i>1），其宽度必须严格小于它下方积木的宽度 3. 对于塔中从下往上数的第i个积木（i>1），其高度必须严格大于它下方积木的高度 4. 塔中可以包含任意数量的积木（至少1个） 请计算小A能够堆叠出的最高塔的总高度。

第一行包含一个整数N，表示积木的数量（1 ≤ N ≤ 1000）。 接下来N行，每行包含两个整数h_i和w_i，分别表示第i个积木的高度和宽度（1 ≤ h_i, w_i ≤ 10^9）。

一行，一个整数，表示最高塔的总高度。

- 样例1解析：选择所有积木，按(7,5) → (6,4) → (5,3) → (4,2) → (3,1)的顺序堆叠（注意是从下到上），总高度为7+6+5+4+3=25 - 样例2解析：选择(8,7) → (7,8)是不合法的（宽度7 < 8但高度8 > 7不满足），正确选择是(5,10) → (6,9) → (7,8) → (8,7)，总高度5+6+7+8=26 - 样例3解析：三个积木无法形成合法的堆叠（任意两个都不满足条件），选择最高的单个积木(3,2)，高度为3 - 对于30%的数据：N ≤ 20 - 对于60%的数据：N ≤ 200 - 对于100%的数据：N ≤ 1000