路过~~

求n个串的最长公共子序列

最简单的dp应该能想到 f[len1][len2][len3]......[lenn]=max(f[len1-1][len2-1]......[lenn-1]+是否len1==len2==len3...lenn,
f[len1-1][len2]....[lenn],f[len1][len2-1]......[lenn])
len表示每个字符串的长度
时间符合
空间开不好
就用hash
hash=(p1+len1*p2+len1*len2*p3....);p代表当前长度,len代表每个串的总长
hash值最大只有3000000

直接用普通的最长公共子序列做

前两组做完把那个序列留下来，跟第三组做，再把结果跟第四组做……

于是全部0ms

但是第一组数据竟然错误行输出……我的程序输出1标准行输出2，实在诡异

不定维度动态规划的题目...

不能贪心

经过吾的无数次提交, 终于摸透了数据的可恶...

我是用状态压缩做的, 我是傻×.

状态压缩函数是 x1 * p[2] + x2 * p[3] + x3 * p[4] + ... + xn.

其中p[i] = (len[i] + 1) * (len[i + 1] + 1) * ... * (len[n] + 1);

对于第八组数据, 这个函数超过maxlongint.

若改掉函数, 那么过不了最后一组.

考虑如下数据

25

aa

aa

aa

..

aa

我就是这样发现我的错误的...

求正解!!!!!!!!

压位DP只A了8组郁闷

数据很弱

排序之后求LCS

强大的题目，垃圾数据

大悲剧

orz 数据太弱 直接找LCS也能过

求标准解法= =

排序也可以过，数据太弱？

hash解决状态

MS做过的

楼下的楼下错解……不可取也~

MS见过这道题,是什么最长公共子序列........

这个是子序列，不是子串。

当N>5时，最小的len一定不会很大，所以可以暴搜，因为以前写过所以直接copy过来。

当n

多谢Lhx教主提醒

我也许应该去写篇论文 叫 论通过率是怎么被刷掉的...Orz..

数组开多少啊

路过。

路过……