Description

上下有两个长度为n、位置对应的序列A、B，
其中数的范围均为1~n。若abs(A[i]-B[j])<= 4，则A[i]与B[j]间可以连一条边。
现要求在边与边不相交的情况下的最大的连边数量。
n <= 10^3
Input

Output

Sample Input

6

1

2

3

4

5

6

6

5

4

3

2

1
Sample Output

5

感想

超级无敌大水题。。
这题是我写完上一篇博客才开始的。。5分钟码完然后1A。。。。。
居然还有这等水题。。

题解

看到1000，很容易知道$n^2$随便过。。
然后看到一个很重要的条件，就是线段不能交叉
换句话说，新匹配的边的两个编号都要比以前的大。。
于是就随便用一个f[i][j]表示a搞完i，b搞完j的最优状态就好了。。
递推式显然，自己看代码吧

扩展

然后我们继续思考，要是没有交叉这个条件怎么办呢？
首先，排序是肯定的
然后好像依然可以差不多地DP，具体我也没认真想，应该处理下细节或分类讨论一下就好了
当然，跑网络流也可以，但是你会发现$n^2$的边会不会太大。。
但这没关系，我们可以用线段树优化建图，因为他连的边都是一段区间啊
不会的可以看这个线段树优化建图好题
这样的话边数和点数都限制在$nlogn$了，然后就可以过了

Code

#include<cstdio>
#include<cstring>
const int N=1005;
int n;
int a[N],b[N];
int f[N][N];
int mymax (int x,int y){
   return x>y?x:y;}
int abs (int x){
   return x<0?-x:x;}
int main()
{scanf("%d",&n);for (int u=1;u<=n;u++)  scanf("%d",&a[u]);for (int u=1;u<=n;u++)  scanf("%d",&b[u]);int ans=0;memset(f,0,sizeof(f));for (int u=1;u<=n;u++){for (int i=1;i<=n;i++)//u和i连 {f[u][i]=mymax(f[u-1][i],f[u][i-1]);if (abs(a[u]-b[i])<=4) f[u][i]=mymax(f[u][i],f[u-1][i-1]+1);ans=mymax(ans,f[u][i]);}}printf("%d\n",ans);return 0;
}