重启系统(等级考试4级 2021-03 T4)
2024-10-12 09:57:15
这道题如果没有一次重启系统的机会就相当于两个最长不下降子序列加在一起。
所以只需要改亿点点即可
把dp分为 dpleft 和 dpright
最长不下降子序列程序:最长上升子序列 II 时间复杂度(nlogn) - 王浩泽 - 博客园 (cnblogs.com)
#include<bits/stdc++.h>using namespace std;const int N=1e5;const int inf=1e9;int main(){ int a[N],dp[N],n; cin>>n; for(int i=1;i<=n;i++) scanf("%d",&a[i]); int len=0; for(int i=1;i<=n;i++) { int l=0,r=len+1; while(l+1!=r) { int m=l+r>>1; if(dp[m]<a[i]) { l=m; } else { r=m; } } dp[r]=a[i]; len=max(len,r); } cout<<len; return 0;}
合在一起即可(还要注意亿点细节)
like
for(int x = 1; x <= n; x++){
ans = max(ans, dpleft[x] + dpright[x + 1]);
}
这里的dpleft[x]应该加上dpright[x+1] 如果用x 和 x 的话 x可能会被用两次。
dpleft 和 dpright 都应该初始化为1
在这里给大家推荐一个函数让后面原来倒着算的最长下降子序列 变成正着算的最长上升子序列。
reverse(a + 1, a + n + 1);
之后再拼拼凑凑变成前一段程序:
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 = 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);
}
}
}
最后再找亿下最大值塞入ans中最后输出即可:
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("%d\n", ans);
return 0;
完整代码:
#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 = 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("%d\n", ans);
return 0;
}
最新文章
- Android QQ群:343816731 欢迎大家加入探讨
- 小谈pointer和relation
- PlayerLog.lua --玩家登录通告
- GCD使用dispatch_semaphore_t创建多线程网络同步请求
- nginx rewrite重写与防盗链配置
- 使用ioctl“实现”自定义的系统调用
- 转载:C++ list 类学习笔记
- ASP.NET获取服务器文件的物理路径
- 依赖注入及AOP简述(十一)——生命周期管理 .
- Vs2010中水晶报表引用及打包
- PHP的反射机制【转载】
- ReactNative入门(1)初识ReactJs
- elasticsearch之分词插件使用
- OO第三次博客
- maven解决omitted for duplicate(依赖冲突)
- NGS基础 - 高通量测序原理
- pc-H5 适配方案
- 10个优秀的jQuery Mobile主题
- MVC与WebApi中的异常过滤器
- linux下mysql忘记密码怎么办
热门文章
- Appscan的安装破解以及使用
- Vue3 企业级优雅实战 - 组件库框架 - 3 搭建组件库开发环境
- [CS61A] Lecture 1&;2&;3. Introduction&;Functions&;Control
- 基于python的数学建模---差分方程
- 系统内置APK并签名并配置AndroidStudio
- oracle第二步创建表空间、用户、授权
- include指令和include动作的区别
- 如何通过Java应用程序压缩PDF文档
- RequestMappingHandlerMapping请求地址映射的初始化流程!
- jdk调度任务线程池ScheduledThreadPoolExecutor工作原理解析