设f1[i]表示以1..i中某个合法序列的长度,而且最后一位是较大的

f2[i]表示以1..i中某个合法序列的长度,而且最后一位是较小的

那么就有$f1[i]=max\{f2[j]+1\},(j<i,h[j]<h[i])$,f2同理

本来想直接建线段树来维护这个最大值的,但是似乎不需要:

对于f1,如果h[i-1]<h[i],那显然从i-1更新过来比较好;但如果h[i-1]>h[i],那其实f[i]=f[i-1],因为这种情况中选i-1一定是比i不亏的,因为i-1更大一点。

f2同理

 #include<bits/stdc++.h>
#define pa pair<int,int>
#define ll long long
using namespace std;
const int maxn=; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int N,h[maxn];
int f1[maxn],f2[maxn]; int main(){
int i,j,k;
N=rd();
for(i=;i<=N;i++) h[i]=rd();
f1[]=f2[]=;
for(i=;i<=N;i++){
if(h[i]>=h[i-]) f1[i]=f1[i-];
else f1[i]=f2[i-]+;
if(h[i]<=h[i-]) f2[i]=f2[i-];
else f2[i]=f1[i-]+;
}
printf("%d\n",max(f1[N],f2[N]));
return ;
}

最新文章

  1. .Net组件程序设计之远程调用(二)
  2. memcache与memcached的区别
  3. 深入JVM-Class装载系统
  4. 通讯录CoreData数据库实现版
  5. 【HDOJ】1042 N!
  6. Android ListView多布局讲解
  7. POJ 2368 巴什博奕
  8. Java项目打包方式分析
  9. Linux--Web应用服务和MySQL数据库
  10. vue 项目界面绘制_stylus_iconfont_swiper
  11. css3 样式过度器 Transition
  12. 新版本微信导致的ios表单bug
  13. Visual Studio VS使用freopen调试控制台闪退
  14. ORA-16447 Redo apply was not active at the target standby database
  15. 使用docker 安装 GITLIB
  16. TimelineJS JSON 数据格式 - 译文 [原创]
  17. python 字符串格式化转换类型
  18. hibernate+pageBean实现分页dao层功能代码
  19. Windows上玩转TensorFlow(一)
  20. AngularJs 第一个自定义指令编写

热门文章

  1. ionic第一坑——ion-slide-box坑(ion-slide分两页的坑)
  2. POJ3469 &amp; 最小割(最大流)模板
  3. Servlet视频学习笔记 57-58 (servlet入门和调用过程)
  4. hdu2647 拓扑序
  5. delphi 在 DragDrop 的时候,滚动 TreeView
  6. 15_会话技术_Cookie
  7. Mysql 8个小时连接断开问题解析
  8. [C++关键字] 内置类型
  9. 【巧妙算法系列】【UVA 11384】 Help is needed for Dexter 正整数序列
  10. php_windows搭建
  11. 4. Traffic monitoring tools (流量监控工具 10个)
  12. 【SQL跟踪工具】SQL Profiler 跟踪器
  13. jQuery-2.DOM---jQuery遍历
  14. Python写日志
  15. SpringBoot与任务
  16. webmin小结
  17. LitePal 数据库使用方法(最新2.0LitePal数据库适用)
  18. Humble Numbers HDU - 1058
  19. JVM运行时内存区域
  20. 【Web前端】清除css、javascript及背景图在浏览器中的缓存