4990: [Usaco2017 Feb]Why Did the Cow Cross the Road II 线段树维护dp
2024-08-21 06:53:03
题目 4990: [Usaco2017 Feb]Why Did the Cow Cross the Road II
链接
http://www.lydsy.com/JudgeOnline/problem.php?id=4990
题面
上下有两个长度为n、位置对应的序列A、B，
其中数的范围均为1~n。若abs(A[i]-B[j]) <= 4，
则A[i]与B[j]间可以连一条边。现要求在边与边不相交的情况下的最大的连边数量。
n <= 10^5。
输入
The first line of input contains N (1≤N≤100,0000).
The next N lines describe the order, by breed ID, of fields on one side of the road;
each breed ID is an integer in the range 1…N
The last N lines describe the order, by breed ID, of the fields on the other side of the road.
Each breed ID appears exactly once in each ordering.
输出
Please output the maximum number of disjoint "friendly crosswalks" Farmer John can draw across the road.
样例输入
6
1
2
3
4
5
6
6
5
4
3
2
1
样例输出
5
题解
考虑二维dp[i][j]表示考虑到<a[i]，b[j]>的最大数目
dp[i][j]=max(dp[i-1][j],dp[i][j-1])
如果ai和bj能够连接,dp[i][j]=max(dp[i-1][j-1]+1)
显然第一维可以优化，然后用个线段树求前缀最大值即可。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+7;
int a[maxn],b[maxn],c[maxn],n,dp[maxn];
struct node{int l,r,x;}t[maxn*4];
void build(int x,int l,int r)
{
t[x].l=l,t[x].r=r;
if(l==r){t[x].x=0;return;}
int mid=(l+r)/2;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
t[x].x=max(t[x<<1].x,t[x<<1|1].x);
}
void update(int x,int l,int r,int v){
int L=t[x].l,R=t[x].r;
if(l==L&&R==r){
t[x].x=v;
return;
}
int mid=(L+R)/2;
if(mid>=l)update(x<<1,l,r,v);
if(mid<r)update(x<<1|1,l,r,v);
t[x].x=max(t[x<<1].x,t[x<<1|1].x);
}
int query(int x,int l,int r)
{
int L=t[x].l,R=t[x].r;
if(l<=L&&R<=r)return t[x].x;
int ans=0,mid=(L+R)/2;
if(mid>=l)ans=max(ans,query(x<<1,l,r));
if(mid<r)ans=max(ans,query(x<<1|1,l,r));
return ans;
}
int main(){
scanf("%d",&n);
build(1,1,n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
scanf("%d",&b[i]);
}
for(int i=1;i<=n;i++){
c[b[i]]=i;
}
for(int i=1;i<=n;i++){
for(int j=-4;j<=4;j++){
if(a[i]+j>0&&a[i]+j<=n){
dp[c[a[i]+j]]=max(dp[c[a[i]+j]],query(1,1,c[a[i]+j]-1)+1);
}
}
for(int j=-4;j<=4;j++){
if(a[i]+j>0&&a[i]+j<=n){
update(1,c[a[i]+j],c[a[i]+j],dp[c[a[i]+j]]);
}
}
}
cout<<query(1,1,n)<<endl;
}最新文章
- 菜鸟学Struts2——Interceptors
- java.lang.String类compareTo()返回值解析
- 【python常用模块】os.path
- 【最短路】埃雷萨拉斯寻宝(eldrethalas) 解题报告
- PC-HTML5-搜索框
- curl多线程类。
- Linux-C语言中gettimeofday()函数的使用方法（转载）
- python 字符串（汉语）获得MD5编码
- add jars和add external jars有什么区别
- 如何在Oracle中复制表结构和表数据 【转载】
- Android基础_多媒体
- LinkedHashMap源码分析
- Arch Linux VMware虚拟机（新手）安装教程
- scrapy基础 之 静态网页实例
- clearfix 用法
- kms可用激活服务器地址|kms可用激活服务器分享
- 使用 systemctl 创建 ss 开机
- 使用jquery插件ajaxfileupload一次上传多个文件，示例
- python sys.stdin、sys.stdout和sys.stderr
- javascript 问题