1014. 登山(LIS模型)
模型 LIS
2023-09-14 09:14:58 时间
蓝桥杯国赛指南,详情见专栏
Question
五一到了,ACM队组织大家去登山观光,队员们发现山上一共有N个景点,并且决定按照顺序来浏览这些景点,即每次所浏览景点的编号都要大于前一个浏览景点的编号。
同时队员们还有另一个登山习惯,就是不连续浏览海拔相同的两个景点,并且一旦开始下山,就不再向上走了。
队员们希望在满足上面条件的同时,尽可能多的浏览景点,你能帮他们找出最多可能浏览的景点数么?
输入格式
第一行包含整数N,表示景点数量。
第二行包含N个整数,表示每个景点的海拔。
输出格式
输出一个整数,表示最多能浏览的景点数。
数据范围
2≤N≤1000
输入样例:
8
186 186 150 200 160 130 197 220
输出样例:
4
难度:简单
时/空限制:1s / 64MB
Ideas
该题需要满足的条件
- 下一个浏览的山的编号要大于前一个山的编号
- 同一座山只浏览一次
- 一旦开始下降就不能上升
我们可以看出浏览山的形状是这样的,原问题就变为求这种形状的子序列最大长度。
以折点为区分点,从左右两边进行两次LIS,将其和加起来长度最大就是res,这里就非常像可以重生的怪盗基德的滑翔机。
我们这里可以先把以a[i]为折点的这种形状的子序列长度存起来,后通过查表找到最大值,实现O(N^3)==》 O(N^2)
Code
需要注意的是折点处我们算了两次,所以需要 f[i]+g[i]-1
# 最长上升子序列模型 ==》 正反上升子序列长度和最大,需要注意折点位置算了两次 O(N^2)
N = 1010
n = int(input())
a = list(map(int,input().strip().split()))
f = [0 for i in range(N)]
g = [0 for i in range(N)]
# 正向
for i in range(n):
f[i] = 1
for j in range(i):
if a[i] > a[j]:
f[i] = max(f[i],f[j]+1)
# 反向
for i in range(n-1,-1,-1):
g[i] = 1
for j in range(n-1,i,-1):
if a[i] > a[j]:
g[i] = max(g[i],g[j]+1)
res = 0
for i in range(n):
res = max(f[i]+g[i]-1,res)
print(res)
相关文章
- Flutter App架构:领域模型
- 【说站】css中盒模型的注意点
- 分享16个我总结的思维模型(程序员必读,受用终身)
- DenseNet模型[通俗易懂]
- 【视频】R语言逻辑回归(Logistic回归)模型分类预测病人冠心病风险|数据分享|附代码数据
- 免费模型资源——精灵之刃
- 【计算机网络】应用层 : 总结 ( 网络应用模型 C/S P2P | 域名解析 DNS | 文件传输协议 FTP | 电子邮件 | 万维网 与 HTTP ) ★★★
- AAAI 2023 | 基于T5的两阶段的多任务Text-to-SQL预训练模型MIGA
- 【EventBus】Subscribe 注解分析 ( Subscribe 注解属性 | threadMode 线程模型 | POSTING | MAIN | MAIN_ORDERED | ASYNC)
- 浏览器层面优化前端性能(1):Chrom组件与进程/线程模型分析
- CSS 盒子模型