USACO 2017 February Contest Gold T2: Why Did the Cow Cross the Road II

题目大意

给你两条由n个点组成的一条直链,点带有点权且每条直链的点权为1-n的排列,你可以随意设置每个链中点排列的顺序,现在要求你在两个链中连线

两个点能连线需满足:

  1. 在不同的链上

  2. 不与前面的线交叉

  3. 点权差值小于等于4

  4. 一个点只能连一条线

求最大可能连线数

题目分析

对于该题,显然有一种 O(N2) 的DP。

令 f[i][j] 为第一行看到第 i 个,第二行看到第 j 个的方案数,则转移方程为

f[i][j] = max(f[i-1][j], f[i][j-1], f[i-1][j-1] + 1( if |a_i-b_j| <= 4 ) ) 

显然,这个复杂度仅仅可以过金组,在铂金是不行的,考虑优化。

观察到 dp值会增加当且仅当 |a_i-b_j| <= 4。所以对于第一行的每个数,我们不必要从头枚举,我们这只需要关注与它大小相差4以内的数即可。

这样处理的话,可以用树状数组优化,做到 O(N logN) ,在输入上有个小Trick。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int MAXN=1e5+10;
 4 
 5 int n;
 6 int a[MAXN],b[MAXN],f[MAXN];
 7 
 8 int BIT[MAXN];
 9 inline int lowbit(int x){return x&(-x);}
10 inline void Update(int x,int v){for(int i=x;i<=n;i+=lowbit(i)) BIT[i]=max(BIT[i],v);}
11 inline int Query(int x){int res=0;for(int i=x;i;i-=lowbit(i)) res=max(res,BIT[i]);return res;}
12 
13 int main(){
14     scanf("%d",&n);
15     for(int i=1;i<=n;++i)
16         scanf("%d",&a[i]);
17     for(int i=1,x;i<=n;++i){
18         scanf("%d",&x);
19         b[x]=i;
20     }
21     for(int i=1;i<=n;++i){
22         for(int j=max(1,a[i]-4);j<=min(n,a[i]+4);++j) f[j]=Query(b[j]-1);
23         for(int j=max(1,a[i]-4);j<=min(n,a[i]+4);++j) Update(b[j],f[j]+1);
24     }
25     printf("%d\n",Query(n));
26     return 0;
27 }

 

上一篇:SAP Customer Experience Extensibility gold rule


下一篇:USACO 2016 February Contest Gold: T1 Circular Barn