var

a:array[1..2000]of string[75];

b:array[1..2000]of boolean;

c:array[1..2000]of integer;

i,j,n,k,s:integer;

procedure pai(l,r:integer);

var yi,yj,y:integer;q:string[75];

begin

if(l=r)then exit;

yi:=l;yj:=r;y:=c[l];q:=a[l];

while (yi

这题有点搞笑，我得到评测结果也很搞笑

显示的是AC但是却没有评测结果？！？郁闷...

var n,j,i,max:longint;a:array[0..2000]of string;

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

begin

readln(n);

fillchar(f,sizeof(f),0);

max:=0;

for i:=1 to n do

begin

readln(a[i]);

j:=i-1;

while (j>0)and(pos(a[j],a[i])1) do dec(j);

if j>0 then f[i]:=f[j]+1;

if f[i]>max then max:=f[i];

end;

writeln(max+1);

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program P1028;

var

a:array[1..2000] of string;

sum:array[1..2000] of integer;

i,j,n,max:integer;

begin

readln(n);

for i:=1 to n do

readln(a[i]);

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

for i:= n downto 1 do

begin

max:=0;

for j:=i+1 to n do

if (pos(a[i],a[j])=1)and(length(a[j])>length(a[i])) and(sum[j]>max) then max:=sum[j];

sum[i]:=max+1;

end;

max:=0;

for i:=1 to n do if max

#include

#include

#define maxn 10000

long n,lis[maxn+10];

char word[maxn+10][100];

int main()

{

FILE *fp;

long i,j,ans;

fp=fopen("link.in","r");

fp=stdin;

fscanf(fp,"%ld",&n);

for(i=1;i

如果不是字典序!有重复!~~~

不过这个直接用DP~O(N*N)!AC!

数据好象有错,他说N

实质就是最长不下降子序列

但是我觉得似乎不能用nlogn的那种方法去做，只能写n2的程序，因为题目要求的不是字典序，不知道对不对......

编译通过...

├ 测试数据 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：答案正确... 0ms

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

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

用类似与DP的方法写，想成是最长不升（降）子序列

在处理包含关系时候，用这个：

pos(a[i],a[j])=1

最后评价是wonderful

for(i=2;i

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

N^2的算法，很“朴素”，但实际上2000的一般是可以承受的。。。

so easy!

感觉上用栈比DP还简单。。

还有，楼上说的那个反例，开始前排个序呗。

实际上应该还可以在维护过程中优化，但是对这题的数据来说，根本不需要

终于2次以内AC了

program p1028;

var

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

n,i,j,k,maxxu,max,xu:longint;

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

procedure qs(l,r:longint);

var

mid,i,j,t:longint;

te:string;

begin

i:=l; j:=r; mid:=a[(l+r) div 2];

repeat

while a[i]mid do dec(j);

if (ij;

if lmaxxu then begin maxxu:=b[i]; end; writeln(maxxu);

end.

数据太水了 只能这么说 o(n^2)能过？？？ 我囧了 （虽然我就是）

恩 栈维护的确很牛B 我学到了 但是提个问题 如果按照楼下的说法 那么看一下的数据 就会发现有点问题

6

i

g

int

integer

intern

internet

这么的话 当插入到第二个时候 就需要重新建一个栈了啊 而且感觉有反例 所以还请好好解释下 谢谢了 （顺便说一下 就算是栈 时间复杂度也不是o(n)的 维护栈的时间 最坏情况下也是o(n) 那么总的时间复杂度下界也是o(n^2)的 所以还是写DP吧 而且更简单 也没反例）

最简单想到的就是最长上升子序列 然后就很无聊了 根本没有任何的字符串处理啊 严重怀疑分类错误 嘎嘎

var

xz:array[1..5000]of string;

s:array[0..5000]of longint;

ans,n:longint;

//=====================================

procedure init;

var

i:longint;

begin

readln(n);

for i:=1 to n do

readln(xz[i]);

s[0]:=0;

ans:=0;

end;

//=====================================

procedure soso;

var

i,j,k:longint;

begin

for i:=1 to n do

begin

s[i]:=0;

for k:=0 to i-1 do

if (k=0)or (xz[k]s[i])

then s[i]:=s[k]+1;

if s[i]>ans

then ans:=s[i];

end;

write(ans);

end;

//=====================================

begin

init;

soso;

end.

var

s:Array[0..2000] of string[75];

f:Array[0..2000] of longint;

i,j,n,ans:longint;

begin

readln(n);

for i:=1 to n do

begin

readln(s[i]);

j:=i-1;

while j>0 do

begin

if pos(s[j],s[i])=1 then

if f[i]ans then ans:=f[i];

end;

writeln(ans);

end.

编译通过...

├ 测试数据 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：答案正确... 0ms

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

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

类似 最长不降子序列求法, 可以用2分法加速