“很难想的一道题不过不难写”—— 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#include 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\n", ans); return 0;}