A32873. 重启系统小明帮助管理一个处理数据的计算系统，有N个待处理的任务，需要按照顺序来完成这些任务，即每次所完成任务的编号都要大于前一个完成任务的编号，且单个任务不可以分解完成。计算系统运行着一个奇怪的保护程序，它限制了系统当前所能处理的数据量不能超过上次完成任务所处理的数据量。重启系统可以使它立刻恢复到最高性能（一开始系统拥有最高性能，最高性能大于任何待处理任务的数据量）。小明有一次重启系统的权限（也…
填空题
较难
知识点
题目描述
重启系统
小明帮助管理一个处理数据的计算系统，有N个待处理的任务，需要按照顺序来完成这些任务，即每次所完成任务的编号都要大于前一个完成任务的编号，且单个任务不可以分解完成。计算系统运行着一个奇怪的保护程序，它限制了系统当前所能处理的数据量不能超过上次完成任务所处理的数据量。重启系统可以使它立刻恢复到最高性能（一开始系统拥有最高性能，最高性能大于任何待处理任务的数据量）。小明有一次重启系统的权限（也可以不使用），你能帮他算出最多能完成几个任务吗？
输入
第一行： N (2 <= N <= 1000) 待处理的任务数
第二行： N个整数，每个任务的数据量
输出
输出只包括一行，这一行只包含一个整数，表示最多能完成的任务数。
样例输入
10
1 5 4 3 2 10 9 8 7 6
样例输出
9
提示
回想一下最长上升子序列问题
参考答案
#include <bits/stdc++.h>
using namespace std;
int dpleft[10005],dpright[10005], a[10005];
int n;
int main() {
scanf("%d",&n);
for (int i = 1;i <= n;i++) {
scanf("%d",&a[i]);
dpright[i] = dpleft[i] = 1;
}
reverse(a + 1, a + n + 1);
for (int i = 1;i <= n;i++) {
for (int j = 1; j < i;j++) {
if(a[i] >= a[j]) {
dpleft[i] = max(dpleft[i],dpleft[j] +1);
}
}
}
for (int i = 2;i <= n;i++) {
dpleft[i] = max(dpleft[i - 1], dpleft[i]);
}
// for(int i = 1; i <= n; i++){
// printf("%d = %d\n", i, dpleft[i]);
// }
for (int i = n - 1; i >= 1; i--) {
for (int j = n; j > i; j--) {
if(a[i] <= a[j]) {
dpright[i] = max(dpright[i], dpright[j] + 1);
}
}
}
for (int i = n - 1; i >= 1; i--) {
dpright[i] = max(dpright[i], dpright[i + 1]);
}
int ans = 0;
for (int x = 1; x <= n; x++) {
ans = max(ans, dpleft[x] + dpright[x + 1]);
}
// printf("---------\n");
// for(int i = 1; i <= n; i++){
// printf("%d = %d\n", i, dpright[i]);
// }
printf("%d\n", ans);
return 0;
}
上一题
下一题