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