http://codevs.cn/problem/1040/
与Codevs_1017_乘积最大很像,都是划分型dp.
给出一个字符串和几个单词,要求将字符串划分成k段,在每一段中求共有多少单词(两个单词不能共享第一个字母),将每一段中的单词个数相加,求最大值.
1040 统计单词个数
2001年NOIP全国联赛提高组
给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入,且保证每行一 定为20个)。要求将此字母串分成k份(1<k<=40),且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一 个单词之后,其第一个字母不能再用。例如字符串this中可包含this和is,选用this之后就不能包含th)(管理员注:这里的不能再用指的是位 置,不是字母本身。比如thisis可以算做包含2个is)。
单词在给出的一个不超过6个单词的字典中。
要求输出最大的个数。
第一行为一个正整数(0<n<=5)表示有n组测试数据
每组的第一行有二个正整数(p,k)
p表示字串的行数;
k表示分为k个部分。
接下来的p行,每行均有20个字符。
再接下来有一个正整数s,表示字典中单词个数。(1<=s<=6)
接下来的s行,每行均有一个单词。
每行一个整数,分别对应每组测试数据的相应结果。
1
1 3
thisisabookyouareaoh
4
is
a
ok
sab
7
用dp[i][k]表示将前i个字符划分成k段时的最优解(与乘积最大类似),那么有转移方程:
dp[i][k]=dp[j][k-1]+([j+1,i]中的单词个数).
这样就需要预处理每一个区间[i,j]中的单词个数.
对于区间[i,j],如果以str[i]开头有单词匹配,那么a[i][j]=a[i+1][j]+1. 否则a[i][j]=a[i+1][j].
写一个match函数来判断就好了.
注意:
1.codevs上的数据好像有点问题,注意读入.
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxl=200+5,maxk=40+5,maxd=10; 5 int n,p,K,s,len; 6 int a[maxl][maxl],dp[maxl][maxl]; 7 char str[maxl],dic[maxd][maxl]; 8 9 bool match(int l,int r){ 10 for(int i=1;i<=s;i++){ 11 int len=strlen(dic[i]+1); 12 if(len>r-l+1) continue; 13 bool flag=true; 14 for(int j=1;j<=len;j++) 15 if(str[l-1+j]!=dic[i][j]) { 16 flag=false; 17 break; 18 } 19 if(flag) return true; 20 } 21 return false; 22 } 23 void pre(){ 24 memset(a,0,sizeof a); 25 for(int i=1;i<=len;i++){ 26 if(match(i,i)) a[i][i]=1; 27 for(int j=i-1;j;j--){ 28 if(match(j,i)) a[j][i]=a[j+1][i]+1; 29 else a[j][i]=a[j+1][i]; 30 } 31 } 32 } 33 void solve(){ 34 pre(); 35 for(int i=1;i<=len;i++) dp[i][1]=a[1][i]; 36 for(int k=2;k<=K;k++) 37 for(int i=k;i<=len;i++) 38 for(int j=k-1;j<i;j++) 39 dp[i][k]=max(dp[i][k],dp[j][k-1]+a[j+1][i]); 40 printf("%d ",dp[len][K]); 41 } 42 void init(){ 43 scanf("%d%d ",&p,&K); 44 int id=0; 45 for(int i=1;i<=p;i++){ 46 char c; c=getchar(); 47 while(c>='a'&&c<='z'){ 48 str[++id]=c; 49 c=getchar(); 50 } 51 } 52 len=id; 53 scanf("%d",&s); 54 for(int i=1;i<=s;i++) scanf("%s",dic[i]+1); 55 } 56 int main(){ 57 freopen("tjdcgs.in","r",stdin); 58 freopen("tjdcgs.out","w",stdout); 59 scanf("%d",&n); 60 while(n--){ 61 init(); 62 solve(); 63 } 64 return 0; 65 }