简答题

重启系统（2024.3四级）

小明帮助管理一个处理数据的计算系统，有N个待处理的任务，需要按照顺序来完成这些任务，即每次所完成任务的编号都要大于前一个完成任务的编号，且单个任务不可以分解完成。计算系统运行着一个奇怪的保护程序，它限制了系统当前所能处理的数据量不能超过上次完成任务所处理的数据量。重启系统可以使它立刻恢复到最高性能（一开始系统拥有最高性能，最高性能大于任何待处理任务的数据量）。小明有一次重启系统的权限（也可以不使用），你能帮他算出最多能完成几个任务吗？

时间限制：1000

内存限制：65536

输入

第一行： N (2 <= N <= 1000) 待处理的任务数第二行： N个整数，每个任务的数据量

输出

输出只包括一行，这一行只包含一个整数，表示最多能完成的任务数。

样例输入

10

1 5 4 3 2 10 9 8 7 6

样例输出

9

提示

回想一下最长上升子序列问题

使用微信搜索喵呜刷题，轻松应对考试！

答案：

要完成最多任务，我们可以采用动态规划的方法来解决这个问题。我们可以定义一个dp数组，其中dp[i]表示以第i个任务为结尾的最长上升子序列的长度。初始化dp数组为1，表示每个任务本身都可以作为一个上升子序列。然后，我们遍历从1到N的任务，对于每个任务i，我们遍历之前的任务j，如果j < i且任务j的数据量小于任务i的数据量，那么我们可以将任务i加入到以任务j为结尾的上升子序列中，更新dp[i]为dp[j]+1。最后，我们找到dp数组中的最大值，即为最多能完成的任务数。

解析：

【喵呜刷题小喵解析】：
这个问题实际上是一个最长上升子序列问题，但是增加了限制条件：系统当前所能处理的数据量不能超过上次完成任务所处理的数据量。这意味着我们不能随意地选择任务来形成上升子序列，而是需要保证每次选择的任务的数据量不超过前一个任务的数据量。

为了解决这个问题，我们可以采用动态规划的方法。首先，我们定义一个dp数组，其中dp[i]表示以第i个任务为结尾的最长上升子序列的长度。然后，我们遍历从1到N的任务，对于每个任务i，我们遍历之前的任务j，如果j < i且任务j的数据量小于任务i的数据量，那么我们可以将任务i加入到以任务j为结尾的上升子序列中，更新dp[i]为dp[j]+1。

最后，我们找到dp数组中的最大值，即为最多能完成的任务数。这个最大值就是最长上升子序列的长度，满足题目中的限制条件。

在样例输入中，任务的数据量为1 5 4 3 2 10 9 8 7 6，我们可以得到的最长上升子序列为1 3 4 6 7 8 9，共7个任务。但是，由于题目中限制了系统当前所能处理的数据量不能超过上次完成任务所处理的数据量，所以我们需要重新考虑任务的选择。我们可以选择的任务为1 3 4 5 6 9 10，共7个任务，这也是满足限制条件的最长上升子序列。但是，如果我们使用一次重启系统，我们可以将系统恢复到最高性能，从而可以处理更大的数据量。在这种情况下，我们可以选择的任务为1 3 4 5 6 7 8 9 10，共10个任务，这就是最多能完成的任务数。

因此，对于样例输入，最多能完成的任务数为9。

创作类型：

原创

本文链接：重启系统（2024.3四级）小明帮助管理一个处理数据的计算系统，有N个待处理的任务，需要按照顺序来

让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！

分享考题

答案：

解析：

最热门资讯

JAVA工程师面试指导--猎头内部资料

常见面试问题100问！