题目描述 Description
给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入,且保证每行一定为20个)。要求将此字母串分成k份(1<k<=40),且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后,其第一个字母不能再用。例如字符串this中可包含this和is,选用this之后就不能包含th)(管理员注:这里的不能再用指的是位置,不是字母本身。比如thisis可以算做包含2个is)。
单词在给出的一个不超过6个单词的字典中。
要求输出最大的个数。
输入描述 Input Description
第一行为一个正整数(0<n<=5)表示有n组测试数据
每组的第一行有二个正整数(p,k)
p表示字串的行数;
k表示分为k个部分。
接下来的p行,每行均有20个字符。
再接下来有一个正整数s,表示字典中单词个数。(1<=s<=6)
接下来的s行,每行均有一个单词。
输出描述 Output Description
每行一个整数,分别对应每组测试数据的相应结果。
样例输入 Sample Input
1
1 3
thisisabookyouareaoh
4
is
a
ok
sab
样例输出 Sample Output
7
目标:前i个字符中划分为j个部分包含的单词数
如果知道i——j包含的单词数,动态规划可推出答案。
若想知道i——j包含的单词数,处理出以每个位置为起点是否有单词、单词长度可推出。
所以:
ans[j][i]表示前j个字符划分为i个部分包含的单词数
预处理:f[i][j] i——j包含的单词数 g[i]=j 以i为起点有长为j的单词
f数组处理:如果i+g[i]-1<=j,那么f[i][j]里包含以i为起点长为j的单词
状态转移:ans[j][i]=max(ans[k][i-1]+f[k+1][j])
java:(没有实现分块)
import java.util.Scanner; public class WordNumber { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // int n = sc.nextInt();//表示有n组测试数据 int p = sc.nextInt();//p表示字串的行数 int k = sc.nextInt();//k表示分为k个部分 String str = "";//p行字母串总串 for (int i = 0; i < p; i++) { //输入p行长度为20的字符串 String s1 = sc.next(); str = str+s1; } int g[] = new int[str.length()];//存放字符串str的第i个位置是否有单词,如果没有为0;如果有个g[i]=该单词的长度 int h[] = new int[str.length()];//存放从0到i区域内单词的个数 int f[][] = new int[str.length()][str.length()];//存放从i到j区域内单词的个数 int ans[][] = new int[str.length()][k+1];//ans[j][k]从0到j区域内分成k份最多单词个数,即为题目要求 int s = sc.nextInt();//字典中单词个数 String sArray[] = new String[s];//存放字典中的单词 for (int i = 0; i < s; i++) { //输入s个字典中的单词 sArray[i] = sc.next(); } for (int i = 0; i < str.length(); i++) { //求出个g[]数组 for (int j = 0; j < sArray.length; j++) { if(i+sArray[j].length()<=str.length()) { if(str.substring(i,i+sArray[j].length()).equals(sArray[j])) { g[i] = sArray[j].length(); break; } } } } if(g[0]!=0) {h[0]++;} //求出h[]数组 for (int i = 1; i < str.length(); i++) { if(g[i]==0) { h[i] = h[i-1]; }else { h[i] = h[i-1]+1; } } for (int i = 0; i < f.length; i++) { //求出f[]数组 for (int j = i; j < f[i].length; j++) { if(i==0) {f[i][j] = h[j];} else{f[i][j] = h[j]-h[i-1];} } } for (int i = 0; i < f.length; i++) { //ans[i][1]==f[0][i] ans[i][1] = f[0][i]; } for (int i = 2; i <= k; i++) { //核心算法 for (int j = i-1; j < f.length; j++) { for (int v = 0; v < j; v++) { ans[j][i] = Math.max(ans[j][i],ans[v][i-1]+f[v+1][j]); } } } // for (int i = 0; i < ans.length; i++) { // for (int j = 0; j < ans[i].length; j++) { // System.out.print(ans[i][j]+" "); // } // System.out.println(); // } System.out.println(ans[f.length-1][k]); } }
c:
#include<cstdio> #include<cstring> #include<iostream> using namespace std; int T,p,k,sum,g[401],f[201][201],ans[201][41]; string s,ss,word[7]; int len_tot,len[7]; void pre() { s.clear(); for(int i=1;i<=6;i++) word[i].clear(); memset(g,0,sizeof(g)); memset(f,0,sizeof(f)); memset(ans,0,sizeof(ans)); } int main() { scanf("%d",&T); while(T--) { pre(); scanf("%d%d",&p,&k); while(p--) { cin>>ss; s+=ss; } len_tot=s.length(); scanf("%d",&sum); for(int i=1;i<=sum;i++) cin>>word[i]; for(int i=1;i<=sum;i++) len[i]=word[i].length(); memset(g,127,sizeof(g)); for(int i=0;i<len_tot;i++) for(int j=1;j<=sum;j++) if(s.substr(i,len[j])==word[j]&&g[i]>len[j]) g[i]=len[j]; for(int i=0;i<len_tot;i++) for(int j=i;j<len_tot;j++) for(int l=i;l<=j;l++) { if(g[l]>400) continue; if(l+g[l]-1<=j) f[i][j]++; } for(int i=0;i<len_tot;i++) ans[i][1]=f[0][i]; for(int i=2;i<=k;i++) for(int j=i;j<len_tot;j++) for(int l=i-1;l<j;l++) ans[j][i]=max(ans[j][i],ans[l][i-1]+f[l+1][j]); printf("%d ",ans[len_tot-1][k]); } }
仅供参考!