begin

s:='';

readln(p,k);

n:=p*20;

for i:=1 to p do

begin

readln(s1);

s:=s+s1;

end;

readln(m);

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

for i:=1 to n do w[i]:=10000;

for i:=1 to m do

for j:=1 to n do

if (a[i]=copy(s,j,length(a[i]))) and (length(a[i])

沙茶题留名……

var

p,k,s:integer;

st:string;

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

b:array[1..200,1..200] of longint;

f:array[1..200,1..40] of longint;

p1:array[1..200,1..40] of boolean;

procedure init;

var

i,j,q:integer;

m,t:string;

begin

assign(input,'in.txt');

reset(input);

assign(output,'out.txt');

rewrite(output);

readln(p,k);

st:='';

q:=0;

for i:=1 to p do

begin

readln(m);

st:=st+m;

end;

readln(s);

for i:=1 to s do

begin

readln(t);

for j:=1 to q do

if t=a[j] then

t:='';

if t'' then

begin

inc(q);

a[q]:=t;

end;

end;

s:=q;

fillchar(b,sizeof(b),0);

fillchar(p1,sizeof(p1),false);

p:=p*20;

end;

function opt(v,k:integer):longint;

var

i:integer;

begin

if p1[v,k] then

exit(f[v,k]);

p1[v,k]:=true;

if k=1 then

begin

f[v,k]:=b[1,v];

exit(f[v,k]);

end;

f[v,k]:=-maxlongint;

for i:=k-1 to v-1 do

if f[v,k]

编译通过...

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

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

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

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

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

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

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

预处理搞了4重循环，所以时间差了一点，

本来第三个点

193，196

注意一下DP范围就好。。。

program va;

var i,j,p,k,max,t,n,q:longint;

s,st,l:string;

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

list:array[0..500] of string;

g,f:array[0..1000,0..1000] of longint;

begin

readln(p,k);

for i:=1 to p do

begin

readln(st);

s:=s+st;

end;

n:=20*p;

readln(t);

for i:=1 to t do

readln(list[i]);

for i:=1 to t-1 do

for j:=2 to t do

if length(list[i])>length(list[j]) then

begin

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

end;

for i:=1 to n do

begin a[i]:=n+1;

for j:=1 to t do

if copy(s,i,length(list[j]))=list[j]

then

begin

a[i]:=i+length(list[j])-1;

break;

end;

end;

fillchar(g,sizeof(g),0);

for i:=1 to n do

for j:=i to n do

for q:=i to j do

if a[q]

很销魂的一题...

到最后也不知道我错哪里了...

所以cheat了第三个点...

关于第三个点过不去的问题,我的情况是这样的

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

这个方程中

F[K,J-1] K必须大于等于J-1 才能做下去

我是这样错的,不知道其他人什么情况

贪心亦可

注意细节

o(n^2)

（可能复杂了点，也许可以优化到o(n)）

#include

#include

#include

typedef struct {

int c,p,k;

char zd[200],a[200];}node;

typedef node st[7];

st T;

int n,s,b[210][50]={0},u[201]={0};

void init()

{

int i,j;

scanf("%d",&n);

for(i=1;i

var a:array[0..201,0..201] of longint;

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

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

c:array[1..6] of longint;

d:array[0..1000] of longint;

i,j,z,p,k,s,n,max,l,h:longint;

s1,s2:string;

procedure work;

begin

for i:=1 to n do

begin

a:=0;

fillchar(d,sizeof(d),0);

for j:=i to n do

begin

a:=a;

if j-max+1=l) and (h+c[z]-1=j) and (d[h]=0)

then begin

inc(d[h]);

inc(a);

end;

end;

end;

end;

end;

begin

readln(p,k);

s1:='';

for i:=1 to p do begin readln(s2);s1:=s1+s2;end;

n:=length(s1);

readln(s);

for i:=1 to s do begin

readln(b[i]);

c[i]:=length(b[i]);

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

end;

work;

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

for j:=1 to k do

for i:=j+1 to n do

for z:=j to i-1 do

if f

动态转移方程易推，f:=f+g[k+1,i],g[a,b]表示从a到b这段的单词数，需要预处理，重复的命令应当用另一变量代替（pos是很费时间的，如果不这样会导致超时）

dp什么？？？？

tire树不就ac了？

编译通过...

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

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

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

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

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

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

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

n^2 的 预处理，反正n才200…………

{a[i]表示 以第i个字符为首 可找到 的 最短 的单词 长度}

fillchar(a,sizeof(a),0);

for i:=1 to n do

for j:=1 to keyn do

if i+length(key[j])-1

经过优化，全0ms~

简单的优化思路就是利用一个区间统计结构。当然也可通过两次dp得到.

字符串DP

第3个点先输出196，改了下变成195，又改了下变成194……说到底是边界的问题，终于193了！！

编译通过...

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

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

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

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

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

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

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

#include

#include

using namespace std;

int main()

{

int p,k;

cin>>p>>k;

char word[500]={},*T;

T=new char [1000];

cin.getline(T,21);

int i,j;

for(i=0;in;

char s[10][500]={};

for(i=0;i>s[i];

for(j=0;j

预处理

for k:=1 to lena do

begin

s2:=s;u:=length(a[k]);

repeat

h:=pos(a[k],s2);

if h>0 then

if not used[h] then begin used[h]:=true;inc(d[h]);inc(c[h+u-1]);s2[h]:=' ';end;

until h0 then inc(u,c[i]);

if d[i]>0 then inc(h,d[i]);

c[i]:=u;d[i]:=h;

end;

for i:=1 to lens do

for j:=i+1 to lens do

b:=c[j]-d;

···