预处理last[i]表示以第i个开始,的合法后缀。

pre[i]表示以第i个结尾,的合法前缀。

那么每一个数a[i],肯定是一个合法后缀last[i] + 一个合法前缀,那么合法前缀的数字要小于a[i],并且最大,bit维护小于等于val的最大值即可。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
const int maxn = 1e4 + ;
int c[maxn];
int lowbit(int x) {
return x & (-x);
}
void upDate(int pos, int val) {
while (pos <= maxn - ) {
c[pos] = max(c[pos], val);
pos += lowbit(pos);
}
}
int ask(int pos) {
int ans = ;
while (pos) {
ans = max(ans, c[pos]);
pos -= lowbit(pos);
}
return ans;
}
int a[maxn];
int n;
int last[maxn], pre[maxn];
void work() {
memset(c, , sizeof c);
for (int i = ; i <= n; ++i) cin >> a[i];
last[n] = ;
for (int i = n - ; i >= ; --i) {
if (a[i] < a[i + ]) {
last[i] = last[i + ] + ;
} else last[i] = ;
}
pre[] = ;
for (int i = ; i <= n; ++i) {
if (a[i] > a[i - ]) {
pre[i] = pre[i - ] + ;
} else pre[i] = ;
}
int ans = ;
for (int i = ; i <= n; ++i) {
ans = max(ans, last[i] + ask(a[i] - ));
upDate(a[i], pre[i]);
}
cout << ans << endl;
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
IOS;
while (cin >> n) work();
return ;
}

最新文章

  1. css知多少(12)——目录
  2. mybatis 小于号 转义
  3. 不再以讹传讹,GET和POST的真正区别
  4. 布隆过滤器(Bloom Filter)详解——基于多hash的概率查找思想
  5. AP_AP系列 - 发票管理分析(案例)
  6. 第三百四十六天 how can I 坚持
  7. OpenShare:前所未有的开放性
  8. CROSSTOOL-NG建立交叉编译工具链
  9. noip 2005 等价表达式
  10. 关于oracle dbms_job 定时执行的内容。
  11. JS-将input输入框写入的小写字母全部转换成为大写字母的JS代码
  12. 解决axios传递参数后台无法接收问题
  13. vSphere Client 搭建Windows server 2008 r2 服务器指南
  14. java判断A字符串是否包含B字符串
  15. Django+xadmin打造在线教育平台(九)
  16. java日期间相隔年月日计算
  17. NIOH
  18. swift class的虚函数表、扩展、@objc修饰、虚函数的派发方式研究
  19. 【CF1009F】Dominant Indices
  20. Sybase数据库常用sql语言

热门文章

  1. win8系统在安装软件时安装framework3.5失败的解决办法
  2. SQL:内连接、左外连接、右外连接、全连接、交叉连接区别
  3. HTML layout高仿QQ GUI
  4. Spring MVC 注解开发详解
  5. DDD领域驱动之干货(二)
  6. hdu-5753 Permutation Bo(概率期望)
  7. vmware tools for linux 安装
  8. 基于Jenkins+Gitlab的自动化部署实战
  9. php获取YouTube视频信息的方法
  10. JSON标准格式