2025年美国计算机奥林匹克（USACO）银级模拟试卷（算法优化与数据结构）-贪心算法解析与应用

一、编程题：最长递增子序列

要求：给定一个整数数组，返回其最长递增子序列的长度。

输入：

第一行包含一个整数n（1≤n≤1000），表示数组的长度。

第二行包含n个整数，表示数组中的元素。

输出：

输出一个整数，表示最长递增子序列的长度。

示例：

输入：

5

12345

输出：

5

输入：

5

54321

输出：

1

二、编程题：背包问题

要求：给定一个物品的重量和价值，以及背包的容量，计算背包能够装入的最大价值。

输入：

第一行包含一个整数n（1≤n≤100），表示物品的