当前位置:网站首页>牛客网:拦截导弹
牛客网:拦截导弹
2022-07-05 13:49:00 【lsgoose】
这题通过一个数学定理将问题转化成了求最长递增子序列的问题。
首先,第一问很明显就是求最长非递减子序列,第二问要用一个定理,可以参考:
Dilworth定理是个啥东东_litble的博客-CSDN博客_dilworth定理
最后转化了问题后,求解就显得十分的简单,数学yyds,代码如下所示:
#include<bits/stdc++.h>
using namespace std;
// 求最长非递减子序列长度
int solve1(vector<int> &height){
int len=height.size();
int res=INT_MIN;
vector<int> dp(len, 1);
for(int i=0;i<len;++i){
for(int j=0;j<i;++j){
if(height[i] <= height[j]){
dp[i]=max(dp[i], dp[j]+1);
}
}
res=max(res, dp[i]);
}
return res;
}
// 求最长递增子序列长度
int solve2(vector<int> &height){
int len=height.size();
int res=INT_MIN;
vector<int> dp(len, 1);
for(int i=0;i<len;++i){
for(int j=0;j<i;++j){
if(height[i] > height[j]){
dp[i]=max(dp[i], dp[j]+1);
}
}
res=max(res, dp[i]);
}
return res;
}
int main(){
int n;
cin>>n;
vector<int> height(n);
for(int i=0;i<n;++i){
cin>>height[i];
}
int res1=solve1(height);
int res2=solve2(height);
cout<<res1<<endl<<res2<<endl;
return 0;
}
边栏推荐
- Assembly language - Beginner's introduction
- 龙芯派2代烧写PMON和重装系统
- Usage, installation and use of TortoiseSVN
- French scholars: the explicability of counter attack under optimal transmission theory
- 不知道这4种缓存模式,敢说懂缓存吗?
- 真正的缓存之王,Google Guava 只是弟弟
- [South China University of technology] information sharing of postgraduate entrance examination and re examination
- Record in-depth learning - some bug handling
- 内网穿透工具 netapp
- Elfk deployment
猜你喜欢
我为什么支持 BAT 拆掉「AI 研究院」
【公开课预告】:视频质量评价基础与实践
redis6主从复制及集群
Attack and defense world crypto WP
面试官灵魂拷问:为什么代码规范要求 SQL 语句不要过多的 join?
研究生可以不用学英语?只要考研英语或六级分数高!
uplad_ Labs first three levels
Data Lake (VII): Iceberg concept and review what is a data Lake
Ordering system based on wechat applet
Laravel框架运行报错:No application encryption key has been specified
随机推荐
Binder communication process and servicemanager creation process
Internal JSON-RPC error. {"code":-32000, "message": "execution reverted"} solve the error
ETCD数据库源码分析——集群间网络层客户端peerRt
js 从一个数组对象中取key 和value组成一个新的对象
stm32逆向入门
Request + BS4 crawl Netease cloud music popular comments
MMSeg——Mutli-view时序数据检查与可视化
When using Tencent cloud for the first time, you can only use webshell connection instead of SSH connection.
Kafaka log collection
几款分布式数据库的对比
asp.net 读取txt文件
嵌入式软件架构设计-消息交互
Could not set property ‘id‘ of ‘class XX‘ with value ‘XX‘ argument type mismatch 解决办法
什么叫做信息安全?包含哪些内容?与网络安全有什么区别?
Introduction to Chapter 8 proof problem of njupt "Xin'an numeral base"
Etcd database source code analysis -- rawnode simple package
Prefix, infix, suffix expression "recommended collection"
MySQL if else use case use
Mmseg - Mutli view time series data inspection and visualization
49. 字母异位词分组:给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的字母得到的一个新单词,所有源单词中的字母通常恰好只用一次。