“很难想的一道题不过不难写”—— Po姐
这道题窝的思考过程十分坎坷。
首先想着纯DP，类似于NOIP Day2T2的方法搞。
设f[i][j]为强制将A[i]与B串中第j个相同字符匹配的LCS，s[i][j]为考虑到A[i]与B串中第j个相同字符匹配（且强制不允许选这个字符之后）的LCS。
从这个状态设计就可以看得出来它既麻烦又sb。
先解释一下为什么要强制不允许选该字符之后——否则会造成交叉：之前的超过了当前字符。
这道题和NOIP2015 Day2T2有一个不同：前者是一个具有特殊性质的LCS问题，而后者需要有一个序列被完全匹配。
所以本题用DP就会产生一系列的问题。比如上面所述的那个状态就有一个很严重的问题：s[1][1]应该是什么？如果B串中第一个A[i]同字符出现在较后面的位置，那么s[1][1]甚至无法转移——因为它依赖于后面的状态，比如A[2]在B串中第一个同字符在A[1]之前，那么就无法转移了。
但是由这个失败的DP我们也能得到一些启示：我们的DP顺序应是按照B串中字符的顺序。如此一来，我们的状态也可以得到简化：f[i]表示以i结尾的LCS长度。考虑LCS的基本特点：当且仅当a[i]=b[j]时，f[i]+1。那么，我们就只需记录A串中每个字符出现的5个位置，按照B串的顺序扫描。对于B[j]，我们找到A串中对应的5个位置，然后f[pos]=max{f[k]| k<pos}+1。注意要按k倒序搞，不然会造成重复加。如何取得最大值呢？线段树用不着：对于A[1..m]的连续区间的最大值，直接用树状数组即可——考虑树状数组求和的原理：一层一层地往上爬，把沿途的长条的值累和。这里，我们只要把每段“长条”维护的值改为本区间内最大值即可。注意各种地方n*5别忘了。
// BZOJ 1264
#include <cstdio>
#include <cstring>
using namespace std;
#define rep(i,a,b) for (int i=a; i<=b; i++)
#define read(x) scanf("%d", &x)
#define fill(a,x) memset(a, x, sizeof(a))
#define dep(i,a,b) for (int i=a; i>=b; i--)
const int N=20000+5, S=6;
int a[N*5], b[N*5], n, C[N*5], cnt[N], pos[N][S], f[N*5], ans=0;
int lowbit(int x) { return x&(-x); }
int max(int a, int b) { return a<=b ? b : a; }
int get_max(int x) {
int ret=0;
for( ; x; x-=x&-x) ret=max(ret, C[x]);
return ret;
}
void update(int x, int w) {
for( ; x<=n*5; x+=x&-x) C[x]=max(C[x], w);
}
int main()
{
read(n);
rep(i,1,5*n) cnt[i]=C[i]=f[i]=0;
rep(i,1,5*n) read(a[i]), pos[a[i]][++cnt[a[i]]]=i;
rep(i,1,5*n) read(b[i]);
rep(i,1,5*n)
dep(j,5,1) {
int p=pos[b[i]][j];
f[p]=max(f[p], get_max(p-1)+1);
update(p, f[p]);
ans=max(ans, f[p]);
}
printf("%d
", ans);
return 0;
}