for p:=1 to k do

for i:=1 to len do

for j:=0 to i-1 do

f[p,i]:=max(f[p,i],f[p-1,j]+d[j+1,i]);

类似加法表达式。

编译通过...

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

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

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

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

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

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

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

最典型的动规.

f表示前i个字符,分成j段,得到的最大单词数目

g表示第z+1个字符到第i个字符,可得的最大单词数目.

f:=f[z,j-1]+g[z+1,i];

可推广至 分段类 的动态规划.

同lovAs感想一样，什么算法也没用，稀里糊涂地光用IF+FOR模拟下来就过了

和1117一样,都属于经典线行DP,只是f:=max{f[k,j-1]+cost[k+1,i]}中的cost[k+1,i]处理不一样

我没有用五重循环，但具体也不知道是什么方法，反正就是稀里糊涂的做出来了。

首先，题目说要分成k个部分，那么，可以向考虑不分的情况，就是先找出整个字符串里有多少个单词。首先看到单词表里最多有六个单词，那样搜索没问题，所以在读入时先找出单词的最长值lon，然后就从每个字母开始向后找，如果这个以字母开头由单词存在，就sum+1,这里不用考虑以此字母开头的单词有多个，反正不影响，找到一个就跳出循环。

在找到单词的时候同时要把这个单词长度方到以开头字母为坐标的一个数组里（jud），然后要考虑分段，我想到了昨天刚做的修理牛棚，当从一个字母后面截断时，为了不截断单词，当然要先截断一个不再单词里的字母，实在没有了，再去截断组成单词的字母，截断时，为了减少损失，当然要使截断的字母他所参与构成的单词数最少，于是我用了一个数组pan，里面记录了每一个坐标对应的字母所构成的单词数，然后将其排序，从小到大找出前k-1个，（分成k段需要切k-1刀）然后用sum减去这个数就搞定了。

单词里面可能会有重复的，需要特殊处理。

编译通过...

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

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

├ 测试数据 03：答案错误...　├ 标准行输出 193

　 ├ 错误行输出 196

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

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

有谁是这样错的???

指点一下!!!!!

我的方程是 f[i][j]=max{f[t]+see(t+1,j)} t

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

没什么要说的 占个楼而已

嘿嘿~

类似于数字游戏～

但不知this中包含is后还能不能有this

动态规划

不知是否可用以下状态转移方程：

f:=f+g[k+1,j](1

请问？？？

谁能发个题解！！！

这题提交了5次..发现原因是少了begin 和end..残念了

先找出以每个字符开头的最短的单词，然后DP

类似于乘积最大。由于每个字母最多只能作为一个单词的起始字母，而且，对于每个字母，由它开始的较短的单词如果被断点截断，那么由它开始的较长的单词（如果存在的话）也会被截断。所以，在选择由某个字母起始的单词的时候，选择较长的不会比选择较短的更优。因此，预处理时需要存储由每个字母开始的最短的单词长度len[i]，并统计任意两个点之间包含的的单词总数g（这一步不必选择比较高级的方法，对区间内以每个字母开头的单词（先判断存不存在）逐个判断末尾是否在区间内即可）。预处理结束之后，就可以模仿乘积最大的转移方程，找到前i个字母中添加j个分断点能够得到的最多的单词数f:=max(f[k,j-1]+g[k+1,i]),1

今天终于下决心,搞定了这个题..................

DP时注意每个变量的取值范围就行了....老题目，解题报告多

var
p,k,n,m,i,j,x,kk,pp,c,cc:longint;
s,ss,t,tt:ansistring;
aa:string[50];
a:array[0..6]of string;
f:array[0..300,0..50]of longint;
d:array[0..300,0..300]of longint;
b:array[0..300]of boolean;
flag:boolean;
function max(x,y:longint):longint;
begin
if x>y then exit(x)
else exit(y);
end;
function pd(tt:string):boolean;
var
j:longint;
begin
for j:=1 to m do
if a[j]=tt then exit(true);
exit(false);
end;
begin
readln(p,k);
for i:=1 to p do begin
readln(aa);
s:=s+aa;
end;
n:=length(s);
readln(m);
for i:=1 to m do readln(a[i]);
for i:=1 to n do
for j:=i to n do
begin
fillchar(b,sizeof(b),true);
for kk:=1 to m do
if (j-i+1)>=length(a[kk]) then
for c:=i to j-length(a[kk])+1 do begin
flag:=true;
for cc:=c to c+length(a[kk])-1 do
if a[kk][cc-c+1]<>s[cc] then begin flag:=false;break;end;
if flag and(b[c])then begin
inc(d[i,j]);b[c]:=false;
end;
end;
end;
fillchar(f,sizeof(f),0);
for i:=1 to n do f[i,1]:=d[1,i];
for j:=2 to k do
for i:=j to n do
for x:=j-1 to i-1 do
f[i,j]:=max(f[i,j],f[x,j-1]+d[x+1,i]);
writeln(f[n,k]);
end.