0

KSASA LV 8 @ 2009-11-07 21:39:26

类似LDS，不用Trie，只要初一的知识就可以了

DP O(n^2) 0ms

你们错的我第一次都看到了

你们一次AC的地方我错了......

0

zhangjie LV 8 @ 2009-11-07 14:44:32

编译通过...

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

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

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

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

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

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

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

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

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

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

水。。。。。。。

0

laz LV 10 @ 2009-11-06 07:49:39

。。。交了3次。

把pos(a[x],a[y])=1 打成pos(a[x],a[y])>0 ..悲剧。

没秒杀。继续优化试试O.O

0

sixhomeland LV 9 @ 2009-11-04 22:08:12

朴素的方法也能秒杀……

（顺便说下，下面是我小号，用trie真是大材小用……权当复习了……）

在加一句：输入的单词是按字典顺序排列

0

qscesz123 LV 8 @ 2009-11-04 22:03:30

我SB了……

用trie又做了一遍……

哎……

0

啊哦嗯 LV 7 @ 2009-11-04 20:51:53

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var a:array[1..2000]of string;b:array[1..2000]of integer;

n,i,j,max:integer; c:boolean;

begin readln(n);

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

for i:=1 to n do begin

c:=true;

j:=i;

while c and(j1)do begin

j:=j-1;

if pos(a[j],a[i])=1 then begin c:=false;b[i]:=b[j]+1;end;

end;

if c then b[i]:=1;

end;

max:=0;

for i:=1 to n do if b[i]>max then max:=b[i];

writeln(max);

end.

DP是什么

0

fjlyzpcr LV 8 @ 2009-11-01 19:32:39

范围是2000

还有一个0在下一行害我没看到 wa掉了

方法很土。。

没超时万幸。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program ex;

var i,j,n,ans:longint;

s:array[1..2000]of ansistring;

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

procedure init;

var i,j:longint;

begin

readln(n);

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

end;

function min(a,b:longint):longint;

begin

if a>b then exit(b) else exit(a)

end;

function max(a,b:longint):longint;

begin

if a>b then exit(a) else exit(b);

end;

procedure dp;

var i,j,len:longint;

begin

filldword(f,sizeof(f)div 4,1);

for i:=1 to n do

for j:=1 to i-1 do

begin

len:=min(length(s[i]),length(s[j]));

f[i]:=max(f[i],ord( copy(s[i],1,len)=copy(s[j],1,len) )*f[j]+1);

end;

end;

begin

init;

dp;

for i:=n downto 1 do if ans

0

qaz674235205 LV 7 @ 2009-10-31 14:45:51

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

用栈处理的！！全部0ms！

时间复杂度O(N)

0

joddy LV 7 @ 2009-10-29 21:00:07

为什么明明我用的DP，程序也和楼上的差不多，最后一组却超时了呢？

0

SDreaming LV 10 @ 2009-10-28 21:39:34

好多杯具啊。这题是让人用栈的！！O(n)而不是DP

0

xiaohulihutu LV 8 @ 2009-10-28 13:17:01

Program ex1;

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

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

n,m,i,j,p,q:longint;

Begin

readln(n);

for i:=1 to n do

begin

readln(a[i]);

end;

b[1]:=1;

for i:=1 to n-1 do

begin

for j:=i downto 1 do

begin

if pos(a[j],a)=1 then

begin

b:=b[j]+1;

break;

end

else

b:=1;

end;

end;

for j:=1 to n do

begin

if p

0

qiaomingda LV 8 @ 2009-10-25 09:25:55

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

记忆化搜索。。居然能过,还只用了9ms。。

0

尖端才子 LV 10 @ 2010-04-06 18:22:02

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

新一次提交此题，因为突然发现可以一边DFS解决……然后瞬间秒杀此题！

具体代码请看

my blog

http://hi.baidu.com/tgrwfskq/blog/item/c639ce26cc95281b8b82a162.html

题解：

因为是有序的，所以相当于一棵Trie树，所以直接DFS遍历，找到最深的一层即可，其层数即是答案。时间复杂度，如果算上读入和pos的时间为O(nl)……因为有字符串操作

{---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|}

强烈BS题目……不是200吗？为啥是2000……

自己也囧了……

pos(s[j],s[i])=1写成了0

……

囧了……

刚看了神牛们写的题解，发现自己太菜了……

我插排+DP=O(N^2)就是一个最长不上升不下降子序列的变形……

事实上，如果字串再短点可以优化一些……

0

明慧 LV 10 @ 2009-10-22 17:15:53

n*50 的算法。。

program vijos_1028;

var

a,b : array[0..3000]of string;

n ,tot : longint;

procedure init;

var

i : longint;

begin

readln(n);

for i:=1 to n do

readln(a[i]);

end;

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

procedure work;

var

i,j : longint;

begin

tot:=1;

b[tot]:=a[1];

for i:=2 to n do

begin

if pos(b[tot],a[i])=1 then

begin

inc(tot);

b[tot]:=a[i];

end

else

begin

for j:=1 to tot do

if pos(b[j],a[i])1 then break;

b[j]:=a[i];

end;

end;

writeln(tot);

end;

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

begin

init;

work;

end.

0

vasile LV 8 @ 2009-10-21 12:16:56

dp_最长上升子序列，只不过这是字符，写个函数就OK了

0

Vicet LV 6 @ 2009-10-14 22:21:38

没用什么复杂算法就做出来了……

于是用穷举，string函数就用了个strlen，

竟然AC了= =

#include

main(){

char s[2000][75];

int len[2000];

int i,j,k,n,tmpn,max=1,fs;

scanf("%d",&n);

for(i=0;i0;i--){

tmpn=1;fs=i;

for(j=i-1;j>=0;j--){

if(len[fs]

0

SecretAgent LV 10 @ 2009-10-13 21:54:27

写个trie然后dfs统计一下就好，

AC后来题解区发现全民DP中...

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

0

Volom@nder LV 8 @ 2009-10-12 22:55:16

水题。。不用过程就ac了。。

var

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

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

n,i,j,max:integer;

begin

readln(n);

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

for i:=n downto 1 do begin

max:=0;

for j:=n downto i do

if copy(a[j],1,length(a[i]))=a[i] then if maxmax then max:=b[i];

writeln(max);

end.

0

peng7621260 LV 9 @ 2009-10-08 10:43:02

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

其实就一最长不降子序列

#include

#include

int N;

char s[2010][100];

int main()

{

scanf("%d",&N);

for(int i=1;i

0

芒果木瓜榴莲 LV 9 @ 2009-10-06 11:37:19

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var

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

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

l,ans:array[1..2000]of longint;

s:string;

begin

readln(n);

for i:=1 to n do

begin

readln(a[i]);

l[i]:=length(a[i]);

end;

for i:=1 to n-1 do

for j:=i+1 to n do

if l[i]>l[j]then begin

s:=a[i];k:=l[i];

a[i]:=a[j];l[i]:=l[j];

a[j]:=s;l[j]:=k;

end;

for i:=1 to n do

begin

max:=0;

for j:=1 to i-1 do

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

ans[i]:=max+1;

end;

max:=0;

for i:=1 to n do if ans[i]>max then max:=ans[i];

writeln(max);

end.

很简单

题解

257 条题解

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

魔族密码

信息

状态

开发

支持

题解

257 条题解

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

魔族密码

信息

状态

开发

支持

还没有账户？

登录