「YbtOJ」递推算法
2021/8/4 22:09:50
本文主要是介绍「YbtOJ」递推算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
划分数列
题目地址
Solution
考虑递推。
设\(f_i\)表示\(a_1\sim a_i\)的最少划分段数,\(p_i\)代表以\(i\)结尾单调不降的一段的起点,\(q_i\)则表示以\(i\)结尾单调不升的一段的起点,注意:起点代表这一段第一个数的前一个坐标。
我们可以得到以下转移方程:
\[\large f_i=\min(f_{p_i}+1,f_{q_i}+1) \]也就是说对于\(a_1\sim a_i\)的分段数可以是由上一个单调不降(升)的数段加上当前这一段(指\(a_{p_i+1}\ or\ a_{q_i+1}\sim a_i\)这一段)。
那如何求\(p_i\)和\(q_i\)呢?
显然分为两种情况:(以求\(p_i\)为例,\(q_i\)同理)
- \(a_i\ge a_{i-1}\),那么\(p_i\)的起点与上一项相同,即\(p_i=p_{i-1}\)。
- \(a_i< a_{i-1}\),那么\(p_i\)的起点更新,\(p_i=i-1\)。
时间复杂度为\(O(n)\)。
Code
#include<bits/stdc++.h> using namespace std; const int N=1e5+7; int f[N],p[N],q[N],a[N]; int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) { p[i]=q[i]=i-1; if(a[i]>=a[i-1])p[i]=p[i-1]; if(a[i]<=a[i-1])q[i]=q[i-1]; f[i]=min(f[p[i]]+1,f[q[i]]+1); } printf("%d",f[n]); return 0; }
这篇关于「YbtOJ」递推算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-19永别了,微服务架构!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?