[BZOJ4990][Usaco2017 Feb]Why Did the Cow Cross the Road II
2024-10-06 12:43:53
Description
Farmer John is continuing to ponder the issue of cows crossing the road through his farm, introduced
in the preceding problem. He realizes that interaction between some pairs of breeds is actually acc
eptable if the breeds are friendly, a property that turns out to be easily characterized in terms of
breed ID: breeds aa and bb are friendly if |a-b|≤4, and unfriendly otherwise. It is ok for cows to
wander into fields designated for other breeds, as long as they are friendly.Given the ordering of
N fields on both sides of the road through FJ's farm (again, with exactly one field for each breed o
n each side), please help FJ determine the maximum number of crosswalks he can draw over his road, s
uch that no two intersect, and such that each crosswalk joins a pair of fields containing two breeds
that are friendly. Each field can be accessible via at most one crosswalk (so crosswalks don't meet
at their endpoints).
上下有两个长度为n、位置对应的序列A、B,
其中数的范围均为1~n。若abs(A[i]-B[j]) <= 4,
则A[i]与B[j]间可以连一条边。现要求在边与边不相交的情况下的最大的连边数量。
n <= 10^5。
Input
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.
注意:两个序列都是全排列
Output
Please output the maximum number of disjoint "friendly crosswalks" Farmer John can draw across the road.
Sample Input
6
1
2
3
4
5
6
6
5
4
3
2
1
1
2
3
4
5
6
6
5
4
3
2
1
Sample Output
5
如果一边的一个位置只可以匹配另一边的一个位置,那么这个问题就是简单的最长上升子序列问题了。
但是这题不同,一个点可以匹配多个点,但是点数不多,于是也可以转化成上面的问题。
但是问题就是,如何保证一个点只被匹配一次,其实简单,我们把一边的一个点可以匹配的点的位置从大到小排序,这样就可以保证这些数里在最长上升子序列中最多只有一个出现。
转化甚是巧妙。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define reg register
inline char gc() {
static const int bs = << ;
static unsigned char buf[bs], *st, *ed;
if (st == ed) ed = buf + fread(st = buf, , bs, stdin);
return st == ed ? EOF : *st++;
}
#define gc getchar
inline int read() {
int res=;char ch=gc();bool fu=;
while(!isdigit(ch))fu|=(ch=='-'), ch=gc();
while(isdigit(ch))res=(res<<)+(res<<)+(ch^), ch=gc();
return fu?-res:res;
}
#define N 100005
int n;
int a[N], b[N];
int pos[N];
int c[N*], cnt, tmp[];
int low[N*], ans; int main()
{
n = read();
for (reg int i = ; i <= n ; i ++) a[i] = read();
for (reg int i = ; i <= n ; i ++) pos[b[i] = read()] = i;
for (reg int i = ; i <= n ; i ++)
{
int top = ;
for (reg int j = max(, a[i] - ) ; j <= min(n, a[i] + ) ; j ++)
tmp[++top] = pos[j];
sort(tmp + , tmp + + top);
for (reg int j = top ; j >= ; j --) c[++cnt] = tmp[j];
}
low[++ans] = c[];
for (reg int i = ; i <= cnt ; i ++)
{
if (c[i] > low[ans]) low[++ans] = c[i];
else {
int t = lower_bound(low + , low + + ans, c[i]) - low;
low[t] = c[i];
}
}
cout << ans << endl;
return ;
}
最新文章
- 域名dns查询_查询域名dns ip地址
- 学习varnish随笔
- SQL疑难杂症【5 】大量数据查询的时候要考虑结果为空的情况
- 设计模式之美:Prototype(原型)
- jQuery编程基础精华03(RadioButton操作,事件,鼠标)
- debian 学习记录-2 -账户 -关机
- Node.js(window)基础(2)——node环境下的模块,模块间调用
- jquery.validate的使用
- 简介支持向量机热门(认识SVM三位置)
- 远程连接你的linux服务器
- /var/log各种日志
- c/C++编译的程序占用的内存分为以下几个部分
- 【Arduino】开源开发板说明
- 编写装饰器实现python请求错误重试功能
- 3、Python函数详解(0601)
- curl java 模拟http请求
- [转载]Python3编码问题详解
- 在Load average 高的情况下如何鉴别系统瓶颈
- APP案例分析之华为浏览器
- dlib landmark+人面识别