正如楼下FancyMouse所说：

固定A[i]，可供A[i]匹配的和能和A[i]匹配的都能在B[j]的循环里做出，因此O(mn)

大概就是这个意思吧：

for i:=1 to n do

begin

k:=0;

for j:=1 to m do

if b[j]

对于每一个a[i]，做一次b[j]的循环，仿造最长上升子序列，找出满足a[i]>b[j]时的max(h[j]),当a[i]=b[j]时h[j]=max(h[j]+1).o(mn);

我晕.....

自己想的优化方法...

但是时间恶心了..o(n^2)(注意是小o)

Accepted 有效得分：100 有效耗时：1719ms

不知大牛们们怎么做到0ms的，本来写了个n^3的超了2个点，又加了些小优化，终于勉强过了。我的思路是这样的，f表示第一组a前i个，第二组b前j个所能达到的最大值。预处理g表示第一组第i个与第二组前j个中相同的数的最后的位置。

状态转移f=max(f[k,g[k,j]])+1(a[i]>a[k],0

陈启峰的题解在哪里????

陳啟峰GG,,,,..我也是三鑫的哦....也是跟謝GM的...但這題我也看不懂.........

可以教教我嗎?...........+我Q:563390730...............

本人可能智力有點問題...5555..........

这就是难度0的题目?????

固定A[i]，可供A[i]匹配的和能和A[i]匹配的都能在B[j]的循环里做出，因此O(mn)

怎么这么简单的题目我想了1h，有时候不要把题目想复杂了

为什么Fp-ZJY的号被封了？什么叫自我抄袭？他楼上那个提交得比较晚，内容和他一模一样。。。都没被封

最长公共子序列...？？

然后再算递增序列么。？

Thank kenin!!Very Much!!

to g20071814:

你这么做不符合动规中的最优子结构。由于要同时保证a1[i]>b,使f尽量大，所以我想应该记录下当上升公共子序列结尾为x时的最长子序列长度之后进行动规才可能保证正确

g20071814:

要搜索的

题意:求两个序列的最长上升公共子序列

zju2432

连样例i/o都不改的……汗

程序贴过来，改两行 一次ac

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 9ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 25ms

├ 测试数据 05：答案正确... 275ms

├ 测试数据 06：答案正确... 494ms

├ 测试数据 07：运行超时|格式错误...

├ 测试数据 08：运行超时|无输出...

├ 测试数据 09：运行超时|无输出...

├ 测试数据 10：运行超时|格式错误...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：60 有效耗时：812ms

看了陈启峰大牛的解题报告才AC的，但还是做了好几次才AC，要注意初始化。

朴素算法o(n^4),可以优化到o(n^2)

我是在LCS上+一个判断,但只对一个!