AtCoder Beginner Contest 344

String Bags

题目

输入字符串 \(T\) 和整数 \(N\)，表示有 \(N\) 个袋子。然后对每个袋子，输入其包含的字符串个数 \(A_{i}\)，以及 \(A_{i}\) 个字符串 \(S_{i,1},S_{i,2},\dots,S_{i,A_{i}}\)。对于每个袋子，我们只能从中选择一个字符串或者不选。输出选择袋子的最少个数，使得按照袋子的编号顺序拼接字符串，能够得到字符串 \(T\)。如果无法得到字符串 \(T\)，则输出 \(-1\)。

数据范围：\(1\leq \operatorname{len}(T)\leq 100\)，\(1\leq N\leq 100\)，\(1\leq A_{i}\leq 10\)，\(1\leq \operatorname{len}(S_{i,j})\leq 10\)。

思路

定义 \(dp[i][j]\) 表示从袋子 \([1,i]\) 中选择袋子的最少个数，使得拼接得到的字符串和 \(T\) 的前缀 \([1,j]\) 相同（下标从 \(1\) 开始）。初始状态和转移方程见代码，算是基本的动态规划，太久没做题加上原题表述有歧义，竟然没做出来。

代码

public static void solve() {
    String t = io.next();
    int n = io.nextInt();

    int m = t.length();
    int[] dp = new int[m + 1];
    Arrays.fill(dp, m + 1);
    dp[0] = 0;

    for (int i = 0; i < n; i++) {
        int z = io.nextInt();
        Set<String> set = new HashSet<>();
        for (int j = 0; j < z; j++) {
            set.add(io.next());
        }

        for (int j = m - 1; j >= 0; j--) {
            for (int k = 1; k <= 10 && k <= j + 1; k++) {
                if (set.contains(t.substring(j - k + 1, j + 1))) {
                    dp[j + 1] = Math.min(dp[j + 1], dp[j + 1 - k] + 1);
                }
            }
        }
    }
    io.println(dp[m] == m + 1 ? -1 : dp[m]);
}