题解：AT_abc344_d [ABC344D] String Bags - Block

前情提要：~~小 L~~积木鱼在某谷上第一篇过审的 tj！

明显是 DP。

然后就开始分析：

状态： $dp_{ij} =$ 有 $i$ 个袋子且匹配 $T$ 的前缀的长度为 $j$ 时所需的最少钱数。

匹配 $T$ 的前缀的长度为 $j$ 就是前 $j$ 个字符与 $T$ 的前 $j$ 个字符相同。

相对简单。

然后看转移。为了方便，咱不妨令 $|S|$ 为字符串 $S$ 的长度，其它的同理。

假设是要将第 $i$ 个袋子里的字符串 $L$ 接到 $S$ 的末尾，那么就只有 $S_{|S|+1}$ 与 $S_{|S|+|L|)}$ 依次对应时才能从 $dp_{(i-1)|S|}$ 转移到 $dp_{i|L|}$ 。

为啥呢？

不对应那你接哪儿去了？不是说好接到末尾吗？那你问啥呢，浪费表情:-(

那我不选呢？

不选你 $j$ 不变不就得了？

所以，转移部分就是：

1
for (int i = 0; i < n; i++) {
2
    for (int j = 0; j < 110; j++) dp[i + 1][j] = dp[i][j];  // 同步过去
3
    int m;
4
    cin >> m;
5
    while (m--) {
6
      ...判断是否满足上面的条件
7
        if (满足) dp[i + 1][j + sl] = min(dp[i + 1][j + sl], dp[i][j] + 1);
8
      }
9
    }
10
  }

上面 dp[i + 1][j + sl] 就是不选，dp[i][j] + 1 就是选。

最后看一下时间复杂度。

$\Theta(NM|S|\cdot|T|)$ 。 $M$ 为袋中字符串数量。

为啥？

你看我们上面的代码，不就是先遍历了一遍 $N$ 个袋子，再遍历字符串数量 $M$ ，每次判断相等挨个比较不就是 $|S|\cdot|T|$ 嘛。

结束~

ACCode:

1
// Problem: D - String Bags
2
// Contest: AtCoder -   Toyota Programming Contest 2024#3（AtCoder Beginner Contest 344）
3
// URL: https://atcoder.jp/contests/abc344/tasks/abc344_d
4
// Memory Limit: 1024 MB
5
// Time Limit: 2000 ms
6
//
7
// Powered by CP Editor (https://cpeditor.org)
8
/*Code by Block_Fish*/
9
#include <bits/stdc++.h>
10

11
#define log printf
12
#define EPS 1e-8
13
#define INF 0x3f3f3f3f
14
#define FOR(i, l, r) for (int(i) = (l); (i) <= (r); ++(i))
15
#define IOS                      \
16
  ios::sync_with_stdio(false); \
17
  cin.tie(nullptr);            \
18
  cout.tie(nullptr);
19

20
using namespace std;
21

22
typedef __int128 i128;
23
typedef long long ll;
24
typedef pair<int, int> PII;
25

26
const int N = 110;
27
int dp[N][N];  // dp[i][j] = 前 i 个袋子中匹配 T 的前缀长度为 j 时所需的最少钱数。
28
string t;
29

30
template <typename T>
31

32
inline T read() {
33
  T sum = 0, fl = 1;
34
  char ch = getchar();
35
  for (; !isdigit(ch); ch = getchar())
36
    if (ch == '-') fl = -1;
37
  for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
38
  return sum * fl;
39
}
40

41
template <typename T>
42

43
inline void write(T x) {
44
  if (x < 0) putchar('-'), write<T>(-x);
45
  static T sta[35];
46
  int top = 0;
47
  do { sta[top++] = x % 10, x /= 10; } while (x);
48
  while (top) putchar(sta[--top] + 48);
49
}
50

51
int main() {
52
  IOS memset(dp, INF, sizeof(dp));
53
  dp[0][0] = 0;
54
  cin >> t;
55
  int tl = t.size(), n;
56
  cin >> n;
57
  for (int i = 0; i < n; i++) {
58
    for (int j = 0; j < 110; j++) dp[i + 1][j] = dp[i][j];
59
    int m;
60
    cin >> m;
61
    while (m--) {
62
      string s;
63
      cin >> s;
64
      int sl = s.size();  // 比较
65
      for (int j = 0; j + sl <= tl; j++) {
66
        bool flag = true;
67
        for (int k = 0; k < sl; k++)
68
          if (t[j + k] != s[k]) {
69
            flag = false;
70
            break;
71
          }
72
        if (flag) dp[i + 1][j + sl] = min(dp[i + 1][j + sl], dp[i][j] + 1);  // 状态转移方程
73
      }
74
    }
75
  }
76
  if (dp[n][tl] > 5e8) dp[n][tl] = -1;  // 过大就是祭了
77
  cout << dp[n][tl] << "\n";
78
  return 0;
79
}

AC记录~

理解万岁！

音乐

音乐

支持与分享

评论区