[BZOJ4993||4990] [Usaco2017 Feb]Why Did the Cow Cross the Road II(DP + 线段树)
2024-08-23 14:26:53
f[i][j]表示当前第i个,且最后一个位置连接到j
第一维可以省去,能连边的点可以预处理出来,dp可以用线段树优化
#include <cstdio>
#include <iostream>
#include <algorithm>
#define N 100001
#define root 1, 1, n
#define ls now << 1, l, mid
#define rs now << 1 | 1, mid + 1, r using namespace std; int n, ans, cnt;
int a[N], pos[N], sum[N << 2], f[N]; inline int read()
{
int x = 0, f = 1;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
return x * f;
} inline int query(int now, int l, int r, int x, int y)
{
if(x > y) return 0;
if(x <= l && r <= y) return sum[now];
int mid = (l + r) >> 1, ret = 0;
if(x <= mid) ret = max(ret, query(ls, x, y));
if(mid < y) ret = max(ret, query(rs, x, y));
return ret;
} inline void update(int now, int l, int r, int x, int d)
{
if(l == r)
{
sum[now] = max(sum[now], d);
return;
}
int mid = (l + r) >> 1;
if(x <= mid) update(ls, x, d);
else update(rs, x, d);
sum[now] = max(sum[now << 1], sum[now << 1 | 1]);
} int main()
{
int i, j, x;
n = read();
for(i = 1; i <= n; i++) x = read(), pos[x] = i;
for(i = 1; i <= n; i++)
{
cnt = 0;
x = read();
for(j = max(1, x - 4); j <= min(n, x + 4); j++) a[++cnt] = pos[j];
sort(a + 1, a + cnt + 1);
for(j = cnt; j >= 1; j--)
{
x = query(root, 1, a[j] - 1) + 1;
f[a[j]] = max(f[a[j]], x);
update(root, a[j], x);
}
}
for(i = 1; i <= n; i++) ans = max(ans, f[i]);
printf("%d\n", ans);
return 0;
}
最新文章
- SVN发布网站
- Nessus导入Cookie进行Web应用安全扫描
- <;记录学习>;京东页面最后一天HTML以及css遇到的问题
- 论--如何通过代码解析plist文件创建对应的控制器,以及控制器中的控件
- Centos上的屏幕保护
- htmlcss笔记--a
- leetcode&mdash;Palindrome 解题报告
- bzoj1004
- TPshop用户模块的数据库表关系
- Java仪器数据文件解析-PDF文件
- poj 3090 Visible Lattice Points(离线打表)
- hadoop.docker.up.problems: Too many levels of symbolic links
- easyui datagrid实现拖动表头
- 关于使用jquery的Ajax结合java的Servlet后台判定用户名是否存在
- am335x 10.1";电容touch 不能识别
- col标签的相关实验
- iOS 类似微博或朋友圈的信息流
- vue-cli脚手架build目录中的webpack.base.conf.js配置文件
- uoj #297. 【CTSC2017】密钥
- Java中变量的使用规则
热门文章
- iphone之打开pdf、doc、xls文件用UIWebView
- VM中python2.7运行skier游戏,shell重启问题!!!!!!
- FATAL org.apache.hadoop.hdfs.server.datanode.DataNode: Initialization failed for Block pool <;registering>; (Datanode Uuid unassigned) service to controller/192.168.1.183:9000. Exiting. java.io.IOExcep
- 利用kubeadm快速部署k8s
- jQuery中Ajax事件beforesend及各参数含义
- Emmet:HTML/CSS代码快速编写神器--20150422
- luogu P2574 XOR的艺术 (线段树)
- python多进程与多线程编程
- java.sql.date 插入数据库没有时分秒
- js获取移动端触摸坐标