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

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

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

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

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

太慢了？怎样预处理才能快一些？？新年快乐！！

o(≧v≦)o~~好棒

边界处理啊

仔细啊 没办法 太粗心了

谁给看看 怎么错了...

program p1118;

const

maxn=200;

maxt=40;

var

s,t:string;

c:array[1..maxn]of boolean;

sum:array[1..maxn,1..maxn]of longint;

d:array[1..maxn,1..maxt]of longint;

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

p:array[1..6,1..maxn]of longint;

l,i,j,k:longint;

n,m:longint;

f:text;

procedure add(w,s:longint);

var

i,j:longint;

begin

for i:=1 to w do

for j:=w+s-1 to n do

inc(sum);

end;

procedure KMP(a,b:string;t:longint);

var

m,i,j:longint;

begin

j:=0;

m:=length(b);

for i:=1 to n do

begin

while (j>0) and (B[j+1]A[i]) do j:=P[t,j];

if B[j+1]=A[i] then j:=j+1;

if j=m then

begin

if c then add(i-m+1,m);

c:=false;

j:=P[t,j];

end;

end;

end;

procedure find(t:longint; b:string);

var

i,j,m:longint;

begin

P[t,1]:=0;

j:=0;

m:=length(b);

for i:=2 to m do

begin

while (j>0) and (B[j+1]B[i]) do j:=P[t,j];

if B[j+1]=B[i] then j:=j+1;

P[t,i]:=j;

end;

end;

begin

readln(n,m);

for i:=1 to n do

begin readln(t); s:=s+t; end;

readln(l);

j:=0;

for i:=1 to l do

begin

readln(t);

if length(t)

预处理+DP

DP过程楼下说了，我主要讲下预处理

for i:=1 to n do

for j:=i to n do

begin

fillchar(hash,sizeof(hash),false);{hash表示某个位置是否已经被占用}

l:=copy(s,i,j-i+1);

for oo:=1 to m do

begin

sb:=l;

pp:=pos(sc[oo],sb);

while pp>0 do

begin

if hash[pp]=false then inc(d);{没有用过就用}

hash[pp]:=true;

sb[pp]:=' ';{标志位置不可再用}

pp:=pos(sc[oo],sb);

end;

end;

换种角度解释，就是假设字符串中每个单词都选，如果出现某两个单词的位置的头部重合，则任取一个。

program Project1;

var s,s1:string; flag:boolean;

p,m,i,j,k,ww,n,oo,len,size,t,max:longint;

mas:array[0..10]of string;

lm,num:array[0..10]of longint;

sum,f,pt:array[0..201,0..201]of longint;

begin

readln(p,m);

readln(s);

for i:=2 to p do

begin

readln(s1);

s:=s+s1;

end;

readln(ww);

size:=0;

for i:=1 to ww do

begin

readln(mas[i]);

lm[i]:=length(mas[i]);

flag:=true;

for j:=1 to size do

if mas[i][1]=mas[pt[j,1]][1] then

begin

flag:=false;

inc(num[j]);

pt[j,num[j]]:=i;

break;

end;

if flag then

begin

inc(size);

pt:=i;

num:=1;

end;

end;

//////////////////////////////////

n:=length(s);

for len:=1 to n do

for i:=1 to n-len+1 do

begin

j:=i+len-1;

sum:=0;

for t:=1 to size do

for p:=i to j do

if (s[p]=mas[pt[t,1]][1]) then

begin

max:=0;

for k:=1 to num[t] do

if (j>=p+lm[pt[t,k]]-1) then

begin

if copy(s,p,lm[pt[t,k]])=mas[pt[t,k]] then begin max:=1; break; end;

end;

inc(sum,max);

end;

end;

///////////////////////////////////

for j:=1 to n do f[1,j]:=sum[1,j];

for i:=2 to m do

for j:=i to n do

for k:=i to j do

if f+sum[k,j]>f then f:=f+sum[k,j];

///////////////////////////////////

writeln(f[m,n]);

end.

sum想用dp求解来着，后来还是没想出来

啊，终于干掉这道题了，DP果然是细节活啊………………

integer = 运行超时|无输出...

longint = Accepted 有效得分：100...

AC率者，非吾之所爱也，亦不甚惜...

var

list:array[0..201,0..201] of longint;

b:array[0..201] of string;

i,j,k,l,n,m,u,p:longint;

str,s,t:string;

function work(stri:string):longint;

var

tot,i,j,l:longint;

st:string;

used:array[0..201] of boolean;

begin

st:=stri;

tot:=0;

fillchar(used,sizeof(used),false);

for i:=1 to k do

begin

st:=stri;

l:=0;

j:=pos(b[i],st);

while j0 do

begin

if used[l+j]=false then inc(tot);

used[l+j]:=true;

l:=l+j;

delete(st,1,j);

j:=pos(b[i],st);

end;

end;

exit(tot);

end;

begin

readln(n,m);

l:=0;

str:='';

for i:=1 to n do

begin

readln(s);

str:=str+s;

end;

readln(k);

for i:=1 to k do

readln(b[i]);

for i:=1 to 20*n do

for j:=1 to m do

for u:=1 to i do

begin

t:=copy(str,u,i-u+1);

l:=work(t);

if list+l>list then

list:=list+l;

end;

writeln(list[20*n,m]);

end.

为什么第三个点错了??????

请大牛指点一下.....orz..

终于3颗星了

很郁闷的时间复杂度...

先预处理,将任意两个字母之间可以产生的最大值加入Have数组.

状态F:前I个字母,分J次的最大值

DP方程:F:=Max{F[K,J-1]+Have[K+1,I];}

主过程: for j:=1 to m do for i:=1 to len do for k:=i-1 downto j-1 do begin t:=have[k+1,i]; if t+f[k,j-1]>f then f:=t+f[k,j-1]; end;

编译通过...

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

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

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

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

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

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

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

统计单词前要注意

2个相同的单词合成1个（否则第四组wa）

还有 a属于b length(a)

f=max(f,f+Sum[t+1,j])

说白了就是石子归并

sum表示从i到j个中单词的个数

f表示冲i到j的最大单词个数

为什么我不懂哈~~

我想知道这个分成k部分是什么意思

直接问最多多少个单词不就成了

分成多少部分会影响总数吗？

天，“把字符串分成k份”我看成了“把字符串分k次”……欲哭无泪……

更无奈的是看错题了仍然得了60分……

大约好像应该是f:=max{f+g}f:前i个字符分成j段时最多单词个数g[a,b]:从第a个字符开始长为b的串中的单词数

感谢zhaojianbo的提醒

谢谢

终于AC了

我疯狂了！！！！！！！

写的好猥琐。。。

注意到题目中有一个非常特殊的地方，就是以串中某个位置的字母为首字母，最多只能分出一个单词。由于在拆分字符串的过程中，如果以某位置为首某个较短单词被截断，那么以该位置为首的较长单词必然也会被截断。也就是说，对于各个位置来说我们选取较短的单词总不会比选取较长的单词所形成的单词少。这样我们可以定义一个在位置 的参数 表示以位置 的字母为首字母，所能形成的最短单词的长度。这样如果在这个位置加上这个单词的长度之内截断，则以该位置为首字母就不能形成单词，否则就可能形成一个单词 。这样对于所有的不同 个首位置，我们只要在各个位置依次对各个单词进行匹配就以得出所对应的 的值，这一部分的复杂度为O(wl2) 。然后是计算把字串分为多个部分的过程中有什么单词可以留下。由于是把字串分为多个部分，故我们类比其他的分割字串的问题，列出动态规划的方程如下：

f[l,k]:=max{f[l-i]+g[l-i+1,i]}

其中.1

马棚问题的变种么……来个预处理，全部0ms