[BZOJ1264][AHOI2006]Match(DP+树状数组)

题目:http://www.lydsy.com:808/JudgeOnline/problem.php?id=1264

分析:

考虑做一般的LCS的时候,更新结果的条件是a[i]==b[j]时候

于是可以先记下a数组中1~n每个数字出现的5个位置

然后依次扫描b[i],b[i]可以和对应a中数字的5个位置更新结果,即f[pos]=max(f[1],f[2],...,f[pos-1])+1

这个找最大的操作就用树状数组就行了

原文地址:https://www.cnblogs.com/wmrv587/p/4232606.html