var n,i,j,mx:integer;

s:array[0..2001]of string;

m:array[0..2001]of integer;

begin

readln(n);

for i:=1 to n do begin readln(s[i]);m[i]:=1;end;

for i:=2 to n do

for j:=1 to i-1 do

if pos(s[j],s[i])=1 then if m[j]+1>m[i] then begin m[i]:=m[j]+1;if mx

数据很弱啊

只要是前缀+1就能AC 不需要知道是上升子序列

var i,j,k,l,m,n:longint;

s:array[0..2000] of string;

a:array[0..2000] of longint;

begin

readln(n);

for i:=1 to n do

readln(s[i]);

for i:=1 to n do a[i]:=1;

for i:=2 to n do

for j:=1 to i-1 do

if (length(s[j])a[i] then

a[i]:=a[j]+1;

for i:=1 to n do

if a[i]>m then m:=a[i];

writeln(m);

end.

第一次 第3点超时

完全一样的程序

第二次 AC

我 囧TZ了！！！

日，我直接输出F[N]了

太水了

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

最长上升数列吧。加了一个pos而已。小学生也可以ＡＣ。

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

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

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

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

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

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

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

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

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

├ 测试数据 10：答案正确... 72ms

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

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

我老老实实排序了O(N^2)最简单的写法

不知道为什么可以不排序,有人讲解没~?

C++可以用string

当a[i].substr(0, a[j].length()) == a[j]时可以把i串加到j串后面

1很重要

不是>0

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

感谢imhy123,

pos(a,b)=1 !

这题有O(N)的算法

维护一个栈 插入当前元素时，若栈顶为其前缀则压栈，否则栈顶元素出栈，继续比较栈顶与当前元素，答案就是栈的最大高度

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

囧.水题居然没发现...

直接秒杀!第1616个...

实验证明：不需要排序，直接DP

我郁闷, 一定要 pos( s[j] , s[i] )=1 才 f[i]:=max{f[i],f[j]+1}(1

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

妈啊，我竟然直接输出f[n];

啊啊啊啊啊啊啊啊啊啊啊啊，4次才AC

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

├ 测试数据 10：答案正确... 119ms

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

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

我加了一个快排..

不知道有没有用...

这道题一开始审错题了(我把'前缀'给丢了)导致把题给弄复杂了..哎..

多谢'hdzhyf''huangdatou'

好水...

是前缀，

所以串s的两个前缀一定相互包含

所以dp时只用找到一个前缀就可以了，用不着最长上升序列的算法

被冷到了!!!!!!!

pos(*,*)=1

千万不能>0!!!

请大家务必写明解题思路

只一大堆程序我们会误以为是抄的~~~~~~~~~

暗黎提醒.....

下界 O(n^2) 的算法，居然都是 0ms。