题目链接
题意理解
首先,用
dp[i][j]
表示把第
[0,i]
个字母(从0开始计数)分成j部分,这其中最大的单词数,那么状态间的拓展关系应该是枚举每个小于i的值,并加上这其中的单词数。
另外,求单词数也是可以用dp的。详细解释见代码。
代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int P, K, S;
static int maxs =
10;
static String string =
"";
static String[] words =
new String[maxs];
static int maxn =
220;
static int[][] sum =
new int[maxn][maxn];
static int[][] dp =
new int[maxn][maxn];
public static void main(String[] args) {
FastScanner fs =
new FastScanner();
P = fs.nextInt();
K = fs.nextInt();
for (
int i =
0; i < P; i++) {
String tString = fs.nextToken();
string += tString;
}
S = fs.nextInt();
for (
int i =
0; i < S; i++) {
words[i] = fs.nextToken();
}
for(
int i =
0; i < string.length(); i++) {
if(starts(i, i)) {
sum[i][i] =
1;
}
for(
int j = i -
1; j >=
0; j--) {
if(starts(j, i)) {
sum[j][i] = sum[j+
1][i] +
1;
}
else {
sum[j][i] = sum[j+
1][i];
}
}
}
/**************************************************/
/**************************************************/
for (
int i =
0; i < string.length(); i++) {
dp[i][
1] = sum[
0][i];
}
for (
int k =
2; k <= K; k++) {
for (
int i = k -
1; i < string.length(); i++) {
for (
int j = k -
2; j < i; j++) {
dp[i][k] = Math.max(dp[i][k], dp[j][k -
1] + sum[j +
1][i]);
}
}
}
System.out.println(dp[string.length() -
1][K]);
}
public static boolean starts(
int l,
int r) {
for(
int i =
0; i < S; i++) {
if(string.substring(l, r+
1).startsWith(words[i])) {
return true;
}
}
return false;
}
public static class FastScanner {
private BufferedReader br;
private StringTokenizer st;
public FastScanner() {
br =
new BufferedReader(
new InputStreamReader(System.in));
}
public String
nextToken() {
while (st ==
null || !st.hasMoreElements()) {
try {
st =
new StringTokenizer(br.readLine());
}
catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
public int nextInt() {
return Integer.valueOf(nextToken());
}
}
}