题意
给定长度为 的序列 ，求最长子序列使得其按 中顺序相邻两数的大小关系是给定字符串 的前缀。
思路
考虑有 简单 DP，设 表示 前缀能与 前缀匹配。
发现我们存的是 ，也就意为这这个 DP 的信息密度非常的低，考虑提高一下信息密度。
大胆猜想我们只用留 中最大的一个 就可以了，写一发就过了，很快啊，考虑证明。
不妨设现在有 与 的两条转移链，我们令 只是前面的转移情况不同使得 ，那么可以证明 一定可以等于 或者 一定可以等于 （然后把相等的那个作为 与 向后归纳）。
我们称前一个转移链中的大小关系为 ，后一个为
我们令 ，若我们要证明的东西存在，则可以调整出这个状况，于是我们有 。
先考虑边界情况，显然，若 或者 不存在，则命题成立。
然后发现若 则有 ，由于 于是 的集合与 的集合是一样的。
那么 ，比如说 ，而因为上面提到过的 ，所以有 ，那我们就知道，，所以任意一个 都是合法的 ，答案仍然更劣。
CODE
具体维护由于只增 只增不减，故可以使用树状数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1000010,FSIZE=1<<26;
int n,a[N],ans;
void cmax(int &x,int y){if(y>x) x=y;}
struct FT{
int a[N];
int query(int x){
int re=0;
for(;x;x-=x&-x) cmax(re,a[x]);
return(re);
}
void modify(int x,int p){for(;x<=n;x+=x&-x) cmax(a[x],p);}
}up,dw;
char BuF[FSIZE],*s=BuF;
template<typename T>void read(T &x){
for(;48>*s||*s>57;++s);
for(x=0;47<*s&&*s<58;x=x*10+(*s++^48));
}
int main(){
fread(BuF,1,FSIZE,stdin);
read(n);
for(int i=0;i<n;++i) read(a[i]);
for(;*s<32;++s);
for(int i=0;i<n;++i){
int x=max(up.query(a[i]),dw.query(n-a[i]+1));
cmax(ans,x);
if(s[x++]=='U') up.modify(a[i],x);
else dw.modify(n-a[i]+1,x);
}
printf("%d\n",ans);
return(0);
}s
|