codeforces1468A LaIS
2022/2/26 23:28:46
本文主要是介绍codeforces1468A LaIS,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
https://codeforces.com/contest/1468/problem/A
这个题是在原本lis的基础上的升级版...
之前一直思考这个题必须得存储最后两个数的信息才能进行状态转移....好吧是我的动态规划还不是太好...
我们还是先考虑最原始的DP,f[i]表示以a[i]结尾的最长的长度。
转移的时候可以考虑分类讨论,以a[i]结尾无外乎两种情况,我们令上一个数为a[j],上上一个为a[k].
1.a[j]<=a[i].在这种情况下,我们发现无论a[k]是什么值,我们都能直接向a[j]后面加上a[i].即
f[i]=max(f[j]+1),(1<=j<=i-1,且a[i]>=a[j])。
2.a[j]>a[i].在这种情况下,我们可以发现a[k]<=a[i]才行。但我们的状态没有记录上上一个数的信息,怎么办?其中一个解决办法就是直接从a[k]转移到a[j],相当于我们直接在a[k]的后面直接加上a[j]与a[i]。发现都是可以加上去的。但我们必须保证他们之间的相对关系是正确的。即:
f[i]=max(f[k]+2),(1<=k<=i-2,且a[i]>=a[k],在[k+1,i-1]之间存在a[j]>=a[i]).
第一个情况,我们可以直接用权值线段树即可。第二种情况,我们可以先找到离a[i]最近的大于等于a[i]的a[j],之后可以在[1,j-1]间找最大值。发现这个题又有权值限制,又有位置限制,可以用主席树进行维护。
点击查看代码
这篇关于codeforces1468A LaIS的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升