传送门

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;
}

  

最新文章

  1. SVN发布网站
  2. Nessus导入Cookie进行Web应用安全扫描
  3. &lt;记录学习&gt;京东页面最后一天HTML以及css遇到的问题
  4. 论--如何通过代码解析plist文件创建对应的控制器,以及控制器中的控件
  5. Centos上的屏幕保护
  6. htmlcss笔记--a
  7. leetcode&mdash;Palindrome 解题报告
  8. bzoj1004
  9. TPshop用户模块的数据库表关系
  10. Java仪器数据文件解析-PDF文件
  11. poj 3090 Visible Lattice Points(离线打表)
  12. hadoop.docker.up.problems: Too many levels of symbolic links
  13. easyui datagrid实现拖动表头
  14. 关于使用jquery的Ajax结合java的Servlet后台判定用户名是否存在
  15. am335x 10.1&quot;电容touch 不能识别
  16. col标签的相关实验
  17. iOS 类似微博或朋友圈的信息流
  18. vue-cli脚手架build目录中的webpack.base.conf.js配置文件
  19. uoj #297. 【CTSC2017】密钥
  20. Java中变量的使用规则

热门文章

  1. iphone之打开pdf、doc、xls文件用UIWebView
  2. VM中python2.7运行skier游戏,shell重启问题!!!!!!
  3. FATAL org.apache.hadoop.hdfs.server.datanode.DataNode: Initialization failed for Block pool &lt;registering&gt; (Datanode Uuid unassigned) service to controller/192.168.1.183:9000. Exiting. java.io.IOExcep
  4. 利用kubeadm快速部署k8s
  5. jQuery中Ajax事件beforesend及各参数含义
  6. Emmet:HTML/CSS代码快速编写神器--20150422
  7. luogu P2574 XOR的艺术 (线段树)
  8. python多进程与多线程编程
  9. java.sql.date 插入数据库没有时分秒
  10. js获取移动端触摸坐标