普及练习场 更要技巧的动规与记忆化 统计单词个数

xiaoxiao2021-02-28  12

题目链接

题意理解

首先,用 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(); } /*--------------------------------------------------------*/ // // // // // 此时需要统计从string.substring(i, j+1)内有多少个单词 // 用sum[i][j]表示 // // // /*--------------------------------------------------------*/ 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]; } } } /**************************************************/ // // // // dp[i][j]表示把[0, i]个字母分成j部分,这其中的单词数 // // // // // /**************************************************/ for (int i = 0; i < string.length(); i++) { dp[i][1] = sum[0][i]; } // k表示被分成多少部分 // i表示前(i+1)个字符 // dp[i][k]表示前[0, i]个字符中的单词数 // dp[j][k-1]表示前[0, j]个字符中的单词数 // sum[j+1][i]表示前[j+1,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) { // TODO Auto-generated catch block e.printStackTrace(); } } return st.nextToken(); } public int nextInt() { return Integer.valueOf(nextToken()); } } }
转载请注明原文地址: https://www.6miu.com/read-1750001.html

最新回复(0)