zoj 3349 dp + 线段树优化
2024-08-28 10:50:13
题目:给出一个序列,找出一个最长的子序列,相邻的两个数的差在d以内。
/*
线段树优化dp
dp[i]表示前i个数的最长为多少,则dp[i]=max(dp[j]+1) abs(a[i]-a[j])<=d
复杂度为O(n ^ 2)
利用线段树优化,线段树保存区间最大值。离散化后便可求出,还要注意 对于叶子节点保存的即为dp的值,每次更改即可,开始一直累加。。。。。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm> using namespace std;
#define lson l,m,rt<<1
#define rson m + 1, r, rt<<1|1
const int maxn = 1e5 + ;
int s[maxn];
int n, d;
int san[maxn], tot;
int sum[maxn << ];
void pushUp(int rt){
sum[rt] = max(sum[rt<<], sum[rt<<|]);
}
void update(int pos, int c, int l, int r, int rt){
if (l == r){
sum[rt] = c;//注意
return ;
}
int m = (l + r) >> ;
if (pos <= m) update(pos, c, lson);
else update(pos, c, rson);
pushUp(rt);
}
int query(int L, int R, int l, int r, int rt){
if (L <= l && R >= r){
return sum[rt];
}
int m = (l + r) >> ;
int ret = ;
if (L <= m) ret = query(L, R, lson);
if (R > m) ret = max(ret, query(L, R, rson));
return ret;
}
int main(){
while (~scanf("%d%d", &n, &d)){
tot = ;
for (int i = ; i <= n; ++i){
scanf("%d", &s[i]);
san[tot++] = s[i];
}
sort(san, san + tot);
tot = unique(san, san + tot) - san; memset(sum, , sizeof(sum));
int ans = ;
for (int i = ; i <= n; ++i){
int pos = lower_bound(san, san + tot, s[i]) - san + ;
int l = lower_bound(san, san + tot, s[i] - d) - san + ;
int r = upper_bound(san, san + tot, s[i] + d) - san;
int que = query(l, r, , tot, ) + ;
//cout << " l = " << l << " r = " << r << endl;
ans = max(ans, que);
//cout << " ans = " << ans << endl;
update(pos, que, , tot, );
}
printf("%d\n", ans);
}
return ;
}
最新文章
- C++ 中静态成员函数访问非静态成员变量的方法
- iOS - 沙盒中,如何判断存在文件、目录
- mq_close
- 教程-隐藏/显示任务栏-程序不在任务显示-全面控制Windows
- php学习之道:php中soap的使用实例以及生成WSDL文件,提供自己主动生成WSDL文件的类库——SoapDiscovery.class.php类
- Theos 工程make package时报错
- 为jEasyUi的日期控件添加一个“清空”按钮----通过修改1.4的easyui.min.js
- JFinal极速开发框架使用笔记(二) 两个问题,一个发现
- 关于Keychain
- Centos 32位 安装 NodeJS
- 前后端分离djangorestframework——路由组件
- npm install 错误 安装 chromedriver 失败的解决办法
- Struts2之ValueStack、ActionContext
- 基于SimpleChain Beta的跨链交互与持续稳态思考
- BZOJ4999: This Problem Is Too Simple!树链剖分+动态开点线段树
- UVa 11178 Morley&#39;s Theorem (几何问题)
- static &; abstract
- windows安装mysql-5.7压缩版详细教程
- git提交代码到码云
- 在Linux上编译使用tcmalloc
热门文章
- 倍福TwinCAT(贝福Beckhoff)常见问题(FAQ)-如何把FBD功能块转换成ST语言
- 【Python3 爬虫】05_安装Scrapy
- 使用 curl() 函数实现不同站点之间注册用户的同步
- spring事务管理源码解析--加了@Transactional注解后Spring究竟为我们做了哪些事情?
- NIO之DatagramChannel
- Atitit.java&#160;jar&#160;hell解决方案-----Djava.ext.dirs&#160;in&#160;ide&#160;envi..
- 关于python ide
- android-studio于java相关
- js中级系列三:前端性能优化
- SpringMVC请求使用@PathVariable获取文件名称并且文件名中存在.导致路径被截取的问题