搜狗网站收录入口,在线做数据图的网站,用ip地址做网站地址有危险,网络营销成功的品牌题目描述 Description给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入#xff0c;且保证每行一定为20个)。要求将此字母串分成k份(1k40)#xff0c;且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当… 题目描述 Description 给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入且保证每行一定为20个)。要求将此字母串分成k份(1k40)且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后其第一个字母不能再用。例如字符串this中可包含this和is选用this之后就不能包含th)管理员注这里的不能再用指的是位置不是字母本身。比如thisis可以算做包含2个is。 单词在给出的一个不超过6个单词的字典中。 要求输出最大的个数。 输入描述 Input Description 第一行为一个正整数(0n5)表示有n组测试数据 每组的第一行有二个正整数(pk) p表示字串的行数; k表示分为k个部分。 接下来的p行每行均有20个字符。 再接下来有一个正整数s表示字典中单词个数。(1s6) 接下来的s行每行均有一个单词。 输出描述 Output Description 每行一个整数分别对应每组测试数据的相应结果。 样例输入 Sample Input 1 1 3 thisisabookyouareaoh 4 is a ok sab 样例输出 Sample Output 7 数据范围及提示 Data Size Hint this/isabookyoua/reaoh 有一点坑的dp #includecstdio
#includecstring
#define LL long long
char ch[210],a[10][210];
LL f[210][10];
int l[10],mn[210];
int p,m,k;
inline int min(int a,int b){return ab?a:b;}
inline int max(int a,int b){return ab?a:b;}
bool mrk(int k,int x)
{if(l[k]x-1p*20)return 0;for(int i1;il[k];i)if(a[k][i]!ch[xi-1])return 0;return 1;
}
int calc(int x,int y)
{int sum0;for(int ix;iy;i)if(mn[i]y)sum;return sum;
}
int main()
{int T;scanf(%d,T);while (T--){memset(mn,127/3,sizeof(mn));memset(ch,0,sizeof(ch));memset(f,-1,sizeof(f));scanf(%d%d,p,m);for (int i1;ip;i)for (int j1;j20;j){char cgetchar();while (ca||cz)cgetchar();ch[20*(i-1)j]c;}scanf(%d,k);for(int i1;ik;i)scanf(%s,a[i]1);for (int i1;ik;i)l[i]strlen(a[i]1);for (int i1;ip*20;i)for (int j1;jk;j)if (mrk(j,i))mn[i]min(mn[i],il[j]-1);f[0][0]0;for(int i1;ip*20;i)for(int j0;ji;j){int tcalc(j1,i);for(int l1;lm;l)if(f[j][l-1]!-1)f[i][l]max(f[i][l],f[j][l-1]t);}printf(%d\n,f[p*20][m]);}return 0;
}转载于:https://www.cnblogs.com/zhber/p/4035907.html
