/*
题目大意：给定一个字符串（长度为20*p，不超过200）和一个包含一些单词
（个数为n，1≤n≤6）的词典，问如何将该字符串分成K（不超过40）份，
使得每份中包含的单词个数之和最大，输出这个最大值。以一个位置为起始点只能统计一个单词。

用a[i][j]表示区间（i,j）内所含的单词个数，可以用暴力计算出所有a[i][j]。
再设f[i][k]为字符串前i个字符分割成k份的最优解，最终答案即是f[20*p][K]
状态转移方程为： f[i][k]=max(f[i][k],f[j][k-1]+a[j+1][i])。(k-1<=j<=i-1)
这个方程怎么理解呢？
其实挺简单的
我们对于当前状态f[i][k] 即是到第i个字符    分割成了k份
那我们必然要找到一个分割成k-1份的状态
然后想办法通过再加上一份来转移到当前状态
所以我们枚举这个加上的这一份
加上的这一份都终点肯定是i   那么我们枚举起点j
因为已经分成了k-1分所以j肯定要>=k-1
而因为是要再加上一份得到到i的状态
所以j<=i-1
所以我们很容易想到
如果我们从j这个地方断开i这一段(即使从j到i这一段作为这最后分的一段)
有价值f[j][k-1]+a[j+1][k]
所以我们取所有满足条件的j所得答案最大值就好了
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=202;
int a[MAXN][MAXN];
int f[MAXN][MAXN];
int v[MAXN];
char c[MAXN];
string b[8];
int p,K,n;

void init()
{
    cin>>p>>K;
    for(int i=1;i<=p;i++)
    {
        for(int j=(i-1)*20+1;j<=(i-1)*20+20;j++)
            cin>>c[j];
    }
    cin>>n;
    for(int i=1;i<=n;i++)
    {  
        cin>>b[i];
        for(int j=1;j<i;j++)
            if(b[i]==b[j])
            {   
                i--,n--;
                break;
            }
    }
}

void geta()
{
    for(int i=1;i<=20*p;i++)//外两层
        for(int j=i;j<=20*p;j++)
        {
            memset(v,0,sizeof(v));//每次尝试一个范围的时候清零
            for(int k=1;k<=n;k++)//枚举字典单词
            {
                long len=b[k].length();//取长度
                for(int ii=i;ii<=j-len+1;ii++)//枚举尝试起点
                {   
                    if (v[ii]) continue;//已经匹配了一个单词(用了这个单词起点不能再用)
                    bool flag=1;//标志变量
                    for(int jj=0;jj<len;jj++)//开始尝试匹配
                        if (c[ii+jj]!=b[k][jj]) //有一个字符不一样
                        {
                            flag=0;
                            break;//直接跳出查找
                        }
                    if (flag) //flag=1说明找到了一个单词
                    {
                        a[i][j]++;
                        v[ii]=1;//标记这个起点已用
                    }
        }
      }
    } 
}

void DP()
{
    for(int k=1;k<=K;k++)
        for(int i=1;i<=20*p;i++)
            for(int j=k-1;j<=i-1;j++) //注意从k-1开始，勿漏情况
                f[i][k]=max(f[i][k],f[j][k-1]+a[j+1][i]);
    cout<<f[20*p][K]<<endl;
}

int main()
{
    init();
    geta();
    DP();
    return 0;
}

注意
1.字典单词有重复的
2.DP中的无效状态

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
char dic[10][200],s[300];
int v[300][300],p,k,n,vis[300],f[300][60];

bool find(int l,int r,int t){
int len=strlen(dic[t]);
for(int i=l;i<=r-len+1;i++){
bool flag=true;
if(vis[i]) continue;
for(int j=0;j<len;j++){
if(s[i+j]!=dic[t][j]) flag=false;
}
if(flag) v[l][r]++;
}
return false;
}

int main(){
scanf("%d%d",&p,&k);
for(int i=1;i<=p;i++){
char t[20];
scanf("%s",t);
for(int j=(i-1)*20+1;j<=i*20;j++) s[j]=t[(j-1)%20];
}
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%s",dic[i]);
for(int j=1;j<i;j++) if(!strcmp(dic[i],dic[j])) i--,n--;

}
//预处理v[i][j]表示[i,j]区间中有多少个单词
for(int i=1;i<=20*p;i++)
for(int j=i;j<=20*p;j++){
memset(vis,0,sizeof(vis));
for(int t=1;t<=n;t++)
if(find(i,j,t)) v[i][j]++;
}
// for(int i=1;i<=20*p;i++){
// for(int j=1;j<=20*p;j++)printf("%d ",v[i][j]);
// printf("\n");
// }
//

//dp过程 定义f[i][j]表示前i个字符 分成j个部分的个数 则f[i][j]=max(f[i][j],f[k][j-1]+v[k+1][i]) 0<=k<=i-1;
for(int j=1;j<=k;j++)
for(int i=1;i<=20*p;i++)
for(int t=j-1;t<i;t++)//这里要从j-1开始 否则会漏
f[i][j]=max(f[i][j],f[t][j-1]+v[t+1][i]);
printf("%d",f[20*p][k]);
return 0;
}

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
char dic[10][200],s[300];
int v[300][300],p,k,n,vis[300],f[300][60];

bool find(int l,int r,int t){
int len=strlen(dic[t]);
for(int i=l;i<=r-len+1;i++){
bool flag=true;
if(vis[i]) continue;
for(int j=0;j<len;j++){
if(s[i+j]!=dic[t][j]) flag=false;
}
if(flag) v[l][r]++;
}
return false;
}

int main(){
freopen("1118.in","r",stdin);freopen("1118.out","w",stdout);
scanf("%d%d",&p,&k);
for(int i=1;i<=p;i++){
char t[20];
scanf("%s",t);
for(int j=(i-1)*20+1;j<=i*20;j++) s[j]=t[(j-1)%20];
}
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%s",dic[i]);
for(int j=1;j<i;j++) if(!strcmp(dic[i],dic[j])) i--,n--;//处理重复的情况

}
//预处理v[i][j]表示[i,j]区间中有多少个单词
for(int i=1;i<=20*p;i++)
for(int j=i;j<=20*p;j++){
memset(vis,0,sizeof(vis));
for(int t=1;t<=n;t++)
if(find(i,j,t)) v[i][j]++;
}
// for(int i=1;i<=20*p;i++){
// for(int j=1;j<=20*p;j++)printf("%d ",v[i][j]);
// printf("\n");
// }
//

//dp过程 定义f[i][j]表示前i个字符 分成j个部分的个数 则f[i][j]=max(f[i][j],f[k][j-1]+v[k+1][i]) 0<=k<=i-1;
for(int j=1;j<=k;j++)
for(int i=1;i<=20*p;i++)
for(int t=j-1;t<i;t++)//这里要从j-1开始 否则会漏
f[i][j]=max(f[i][j],f[t][j-1]+v[t+1][i]);
printf("%d",f[20*p][k]);
return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAX 500
using namespace std;
const int MAXN = 500;

char s0[30][30], w[MAXN], d[10][50];
int f[MAXN][MAXN][10], len[10], num[MAXN], all[MAXN][MAXN];

int main()
{
int p, k, tot = 0, s;
scanf("%d%d", &p, &k);
for(int i=1; i<=p; i++)
scanf("%s", &s0[i][1]);
for(int i=1; i<=p; i++)
for(int j=1; j<=20; j++){
tot++;
w[tot] = s0[i][j];

}
scanf("%d", &s);
for(int i=1; i<=s; i++){
scanf("%s", d[i]);
len[i] = strlen(d[i]);
}
for(int i=1; i<=tot; i++)
num[i] = MAX;
for(int i=1; i<=tot; i++)
for(int j=1; j<=s; j++)
if(!strncmp(&w[i], d[j], len[j]))
num[i] = min(num[i], i+len[j]-1);
for(int i=1; i<=tot; i++)
for(int j=i; j<=tot; j++)
for(int z=i; z<=j; z++)
if(num[z] <= j)
all[i][j]++;
int sum = 0;
for(int i=1; i<tot; i++)
for(int j=i+1; j<=tot; j++)
for(int z=i; z<=j; z++)
if(num[z] <= j)
f[i][j][1]++;
for(int i=2; i<=k; i++)
for(int j=1; j<tot; j++)
for(int z=j+1; z<=tot; z++)
for(int y=j; y<z; y++)
f[j][z][i] = max(f[j][y][i-1]+f[y+1][z][i-1], f[j][z][i]);
printf("%d", f[1][tot][k]);
return 0;
}
DP
AC一百题留念，多谢各位（SG，PXL，LYM，SW）的支持。如有疑问，共同进步
再次鸣谢

#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define for1(v,a,b) for (int v=a;v<=b;v++)
#define for2(v,a,b) for (int v=a;v>=b;v--)
using namespace std;
char s[201],word[10][201];
int f[201][201][41],sum[201][201],len[10];
int n,k,p,part;
void Init(){
char ch;
int pos;
for1(i,0,p-1){
scanf("%c",&ch);
for1(j,1,20)
scanf("%c",&s[i*20+j]);
}
scanf("%d",&k);
scanf("%c",&ch);
for1(i,1,k){
pos=0;
while (scanf("%c",&ch),(ch>='a')&&(ch<='z'))
pos++,word[i][pos]=ch;
len[i]=pos;
}
n=20*p;
}
void check(int x,int y){
bool flag=true;
for1(i,1,len[y])
if (s[x+i-1]!=word[y][i]){
flag=false;
break;
}
if (!flag) return;
for1(i,1,x){
sum[i][x+len[y]-1]++;
f[i][x+len[y]-1][0]=sum[i][x+len[y]-1];
}
for1(i,x+len[y]-1,n){
sum[x][i]++;
f[x][i][0]=sum[x][i];
}
}
int main(){
//freopen("p1.in","r",stdin);
scanf("%d%d",&p,&part);
Init();
for1(i,1,n)
for1(j,1,k)
if (i+len[j]<=n+1) check(i,j);
for1(t,1,part)
for1(i,1,n)
for1(j,i+1,n)
for1(h,i+1,j-1)
f[i][j][t]=max(f[i][j][t],f[i][h][t-1]+f[h+1][j][t-1]);
printf("%d",f[1][n][part]);
return 0;

}

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.

预处理耗了我很多时间
还是参考了大神

哪里不对啊？
const
maxn=500;
var
str:string;
word:array[1..50]of string;
s1:array[1..maxn]of string;
p,k,m,n,s:integer;
list:array[1..maxn,1..maxn]of integer;

function work(str:string):integer;
var
total,i,j,l:integer;
used:array[1..maxn]of boolean;
st:string;
begin
fillchar(used,sizeof(used),false);
total:=0;
for i:=1 to s do
begin
st:=str;
l:=0;
j:=pos(word[i],st);
while j<>0 do
begin
if not used[1+j] then
inc(total);
delete(st,1,j);
used[1+j]:=true;
l:=1+j;
j:=pos(word[i],st);
end;
end;
work:=total;
end;

procedure try;
var
i,j,l,u:integer;
begin
for i:=1 to 20*p do
for j:=1 to k do
for u:=1 to i do
begin
l:=work(copy(str,u,i+1-u));
if list[u-1,j-1]+l>list[i,j] then
list[i,j]:=list[u-1,j-1]+l;
end;
end;

begin
writeln('input p and k');
readln(p,k);
for m:=1 to 20*p do
for n:=1 to k do
list[m,n]:=0;
writeln('input string');
for m:=1 to p do
begin
readln(s1[m]) ;
str:=str+s1[m];
end;
writeln('input s');
readln(s);
writeln('word');
for m:=1 to s do
readln(word[m]);
try;
write(list[10*p,k]);
end.

program nanti;
const maxl=200;
type ch=string[maxl];
var n,p,k,s,l,i,max:longint;
word:array[1..6] of ch;
s1:ch;
str:array[1..10] of string[20];
f:array[1..maxl] of integer;
len:array[1..maxl] of longint;
g:array[1..maxl,1..maxl] of byte;
function plus(str:ch):integer;
var
l1,r,i,j,x:integer;
b:array[1..200] of boolean;
begin
x:=0;
l1:=length(str);
fillchar(b,sizeof(b),true);
for j:=1 to l1 do
if (word[j]=copy(str,i,r)) and b[i] then
begin
b[i]:=false;x:=x+1;
end;
plus:=x;
end;
procedure calclen;
var i,j:integer;
begin
for i:=1 to l do len[i]:=200;
for i:=1 to l do
for j:=1 to s do
if copy(s1,i,length(word[j]))=word[j] then if
len[i]>length(word[j]) then len[i]:=length(word[j]);
end;
procedure calcg;
var i,j:integer;
begin
fillchar (g,sizeof(g),0);
for i:= l downto 1 do
begin
if len[i]=1 then g[i,i]:=1;
for j:= l-1 downto 1 do if len[j]<=i-j+1 then g[j,i]:=g[j+1,i]+1
else g[j,i]:=g[j+1,i];
end;
end;
procedure calc;
var i,j,m,maxt,t:integer;stri:string;
begin
for i:= 1 to l do
f[i]:=plus(copy(s1,1,i));
for i:= 2 to k do
begin
for j:=l downto 1 do
begin
maxt:=0;
for m:=i-1 to j-1 do
begin
t:=f[m]+g[m+1,j];
if t>maxt then maxt:=t;
end;
end;
end;
end;
begin
assign(input,'e:\in.txt');assign(output,'e:\out.txt');
reset(input);rewrite(output);
readln(p,k);
s1:=' ';
for i:= 1 to p do
begin
readln(str[i]);
s1:=s1+str[i];
end;
l:=length(s1);
readln(s);
for i:= 1 to s do
begin
readln(word[i]);
calclen;
calcg;
calc;
writeln(f[l]);
end;
close(input);close(output);
end.

怎么有错？？？？！！！！！

#include<cstring>
#include<iostream>
using namespace std;
int word[201][201],dp[201][201][41],p,k,s,max1,le[6],len,i,j,l,m,x,st;
bool yes;
char c[21],w[6][10],c0[201],c1[201];
main()
{
cin>>p>>k;
for(j=0;j<p;j++)
{
cin>>c;
if(j==0)
strcpy(c0,c);
else
strcat(c0,c);
}
len=strlen(c0);
cin>>s;
for(j=0;j<s;j++)
{
cin>>w[j];
le[j]=strlen(w[j]);
}
for(i=0;i<len;i++)
for(j=0;j<len;j++)
word[i][j]=0;
for(i=len-1;i>=0;i--)
for(j=len-1;j>=0;j--)
{
for(l=0;l<s;l++)
{
yes=0;
if(c0[j]==w[l][0]&&le[l]<=i-j+1)
{
yes=1;
for(m=0;m<le[l];m++)
if(c0[j+m]!=w[l][m])
{
yes=0;
break;
}
}
if(yes)
break;
}
if(yes)
word[j][i]=word[j+1][i]+1;
else
word[j][i]=word[j+1][i];
}
for(st=1;st<=k;st++)
for(i=0;i<len-st+1;i++)
for(j=i+st-1;j<len;j++)
{
if(st==1)
{
dp[i][j][st]=word[i][j];
continue;
}
for(max1=0,l=i+st-2;l<j;l++)
{
x=dp[i][l][st-1]+word[l+1][j];
if(x>max1)
max1=x;
}
dp[i][j][st]=max1;
}
cout<<dp[0][len-1][k];
}

sos

var
i,j,k,k1,k2,p,s,max,m:longint;
a:array[1..100] of string;
zd:array[1..6] of string;
str:string;
begin
readln(p,k);
for i:=1 to p do readln(a[i]);
readln(s);
for i:=1 to s do readln(zd[i]);
m:=0; max:=0;
repeat
inc(max);
for i:=1 to 20 do begin
str:=a[max][i];
for k1:=1 to s do if str=zd[k1] then inc(m);
for j:=i+1 to 20 do begin
str:=str+a[max][j];
for k2:=1 to s do if str=zd[k2] then inc(m);
end;
end;
until max=p;
writeln(m);
readln; readln;
end.

program miaoshu;

var
i,j,k,k1,k2,p,s,max,m:longint;
a:array[1..100] of string;
zd:array[1..6] of string;
str:string;
begin
readln(p,k);
for i:=1 to p do readln(a[i]);
readln(s);
for i:=1 to s do readln(zd[i]);
m:=0; max:=0;
repeat
inc(max);
for i:=1 to 20 do begin
str:=a[max][i];
for k1:=1 to s do if str=zd[k1] then inc(m);
for j:=i+1 to 20 do begin
str:=str+a[max][j];
for k2:=1 to s do if str=zd[k2] then inc(m);
end;
end;
until max=p;
writeln(m);
readln; readln;
end.

program miaoshu;

var
i,j,k,k1,k2,p,s,max,m:longint;
a:array[1..100] of string;
zd:array[1..6] of string;
str:string;
begin
readln(p,k);
for i:=1 to p do readln(a[i]);
readln(s);
for i:=1 to s do readln(zd[i]);
m:=0; max:=0;
repeat
inc(max);
for i:=1 to 20 do begin
str:=a[max][i];
for k1:=1 to s do if str=zd[k1] then inc(m);
for j:=i+1 to 20 do begin
str:=str+a[max][j];
for k2:=1 to s do if str=zd[k2] then inc(m);
end;
end;
until max=p;
writeln(m);
readln; readln;
end.

怎么错了？

编译成功

foo.pas(12,53) Warning: Variable "s" does not seem to be initialized
foo.pas(26,21) Warning: Variable "v" does not seem to be initialized
foo.pas(33,40) Warning: Variable "f" does not seem to be initialized
测试数据 #0: Accepted, time = 15 ms, mem = 1424 KiB, score = 20
测试数据 #1: Accepted, time = 0 ms, mem = 1388 KiB, score = 20
测试数据 #2: Accepted, time = 15 ms, mem = 1388 KiB, score = 20
测试数据 #3: WrongAnswer, time = 0 ms, mem = 1388 KiB, score = 0
测试数据 #4: Accepted, time = 0 ms, mem = 1388 KiB, score = 20
WrongAnswer, time = 30 ms, mem = 1424 KiB, score = 80

var
p,k,i,j,n,m,t,l,x,y,g:longint;
z,s:ansistring;
u:array[1..250]of boolean;
w:array[0..10]of ansistring;
v:array[0..250,0..250]of longint;
f:array[0..250,0..250]of longint;
function max(a,b:longint):longint;
begin if a>b then exit(a) else exit(b); end;
begin
fillchar(u,sizeof(u),false);
readln(p,k); for i:=1 to p do begin readln(z); s:=s+z; end;
readln(m); l:=maxlongint; for i:=1 to m do readln(w[i]);
for i:=1 to m-1 do
for j:=i+1 to m do
if length(w[j])<length(w[i]) then
begin w[0]:=w[j]; w[j]:=w[i]; w[i]:=w[0]; end;
for i:=1 to m do
for j:=length(w[i]) to length(s) do
if (copy(s,j-length(w[i])+1,length(w[i]))=w[i])
and(not(u[j-length(w[i])+1])) then
begin
u[j-length(w[i])+1]:=true;
for x:=1 to j-length(w[i])+1 do
for y:=j to length(s) do
inc(v[x,y]);
end;
for i:=1 to length(s)-1 do
begin
if k>i+1 then g:=i+1 else g:=k;
for j:=i+1 to length(s) do
if v[i+1,j]>0 then
for t:=1 to g do f[t,j]:=max(f[t,i]+v[i+1,j],f[t,j]);
end;
writeln(f[k,length(s)]);
end.

帮忙看看哪里错了

#01: Accepted (235ms, 6840KB)

#02: Accepted (200ms, 6840KB)

#03: Accepted (211ms, 6840KB)

#04: Accepted (426ms, 6840KB)

#05: Accepted (395ms, 6840KB)

Accepted / 100 / 1468ms / 6840KB

程序写得很暴力也过？

有这种错的人吗？

编译通过...

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

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

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

├ 测试数据 04：答案错误...　

├ 标准行输出 125

　├ 错误行输出 158

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

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

Unaccepted 有效得分：80 有效耗时：0ms

100AC

400递交

竟然是cheat5555555555555555555555555555555555555555555555555

program p1118;

var

dp:array[1..200,1..200,0..200]of longint;

f:array[1..200]of boolean;

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

s,s1:string;

p,p1,k,n,m,i,j,q,len,ans:longint;

procedure qsort(p,q:longint);

var i,j,x,t:longint;c:string;

begin

if p>=q then exit;

i:=p;

j:=q;

x:=length(word[(i+j)shr 1]);

while i

编译通过...

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

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

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

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

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

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

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

用ansistring 0msAC

program p1;

var strlong:ansistring;

strread:string;

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

len:array[1..6] of integer;

sum:array[0..200,0..200] of integer;

f:array[0..200,0..40] of integer;

p,k,i,j,q,w,s,longbool:integer;

begin

readln(p,k);

readln(strlong);

for i:=2 to p do

begin

readln(strread);

strlong:=strlong+strread;

end;

readln(s);

for i:=1 to s do

begin

readln(word[i]);

len[i]:=length(word[i]);

end;

{if (s=1)and(word[1]='aaaaa')and(p=10)and(k=4) then

begin

writeln('193');

halt;

end; }

for i:=1 to 20*p do

begin

longbool:=maxint;

for j:=1 to s do

if (copy(strlong,i,len[j])=word[j])and(len[j]f then

f:=f[j-1,k-1]+sum[j,i];

writeln(f[20*p,k]);

end.