题目大意:给你两个序列,你可以两个序列的点之间连边

要求:1.只能在点权差值不大于4的点之间连边

2.边和边不能相交

3.每个点只能连一次

表示第一个序列进行到 i,第二个序列进行到 j,最多连的边数,容易得到方程:

不连边:

连边:

实际是这样的,每个位置如果想连边,就要从能连边的位置之前找最大值,即

直接转移不可取,由于最多只从9个位置转移,我们可以缩减一维,用记录b序列进行到位置 的最大连边数,再用树状数组维护的最大前缀和方便转移

 #include <bits/stdc++.h>
#define N 200100
#define ll long long
using namespace std; int n,ans;
int a[N],b[N],hx[N],f[N],s[N];
void update(int x,int w) {for(int i=x;i<=n;i+=(i&(-i))) {s[i]=max(s[i],w);}}
int query(int x) {int ans=; for(int i=x;i>;i-=(i&(-i))) {ans=max(ans,s[i]);} return ans;} int main()
{
//freopen("Testdata.in","r",stdin);
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int i=;i<=n;i++) scanf("%d",&b[i]);
for(int i=;i<=n;i++) hx[b[i]]=i;
for(int i=;i<=n;i++)
{
for(int j=max(,a[i]-);j<=min(n,a[i]+);j++)
f[hx[j]]=query(hx[j]-);
for(int j=max(,a[i]-);j<=min(n,a[i]+);j++)
update(hx[j],f[hx[j]]+);
}
printf("%d\n",query(n));
return ;
}

最新文章

  1. UEditor百度富文本编辑器--让编辑器自适应宽度的解决方案
  2. UIBezierPath-绘制基本图形
  3. 老王讲自制RPC框架.(三.ZOOKEEPER)
  4. Javascript/jQuery 获取地址栏URL参数的方法
  5. 【vijos1900】 学姐吃寿司
  6. UISearchController Attempting to load the view of a view controller while it is deallocating is not allowed and may result in undefined behavior
  7. SQLAlchemy一对多总结
  8. Cmd命令
  9. 300. Longest Increasing Subsequence
  10. #include &lt;QPushButton&gt;
  11. bresenham算法的FPGA的实现2
  12. Javascript DOM 02 在&lt;ul&gt;中创建、删除 &lt;li&gt;
  13. HTML5学习笔记&lt;三&gt;: HTML5样式, 连接和表格
  14. C语言第五次博客作业
  15. DragVideo,一种在播放视频时,可以任意拖拽的方案
  16. 解决linux root 认证失败的问题
  17. CSS3 - @keyframes
  18. shit vue &amp; shit iview
  19. html button 点击 显示倒计时秒数
  20. Android开发工程师文集-Fragment,适配器,轮播图,ScrollView,Gallery 图片浏览器,Android常用布局样式

热门文章

  1. weex手机端安全键盘
  2. python装饰器实现登陆验证
  3. 【ACM-ICPC 2018 沈阳赛区网络预赛 K】Supreme Number
  4. jqury+animation+setTimeOut实现渐变显示与隐藏动画
  5. 日志log配置理解
  6. 初探swift语言的学习笔记十(block)
  7. 英语发音规则---P字母
  8. 新东方雅思词汇---6.1、oppose
  9. hdoj--1201--18岁生日(模拟)
  10. HTML5学习笔记(三):标识文本的语义元素