【题解】String Bags 题解

· · 题解

\mathtt{Pre\ Explanation}

口胡出奇迹！STL 出奇迹！

本题解中 |s| 表示字符串 s 的长度。

\mathtt{Solution}

作为一位合格的 OIer，你第一眼看到本题的想法是：暴力或者贪心。暴力在 Atcoder 赛制中显然不可取，于是你考虑贪心。

你在想：贪心的策略应该是每组选择最长的那个？可是不行啊，万一你选了最长的，后面接不上了怎么办？很有可能选个短的，后面再选个短的就可以接上？

既然贪心不行，那么你就开始思考 DP。你参考 LIS 的定义方法，决定定义 f_i 为凑出 T 的前 i 位的最小代价。这个时候你又发现你需要保证每个组只能选一个，为了不重复选择，你想起了做 01 背包时的状态定义，选择增加一维，于是你把定义改成了 f(i,j) 代表用前 i 组的字符串凑出 T 的前 i 位的最小代价。

有了状态定义，你开始考虑转移。对于第 i 组，你发现可以啥也不做，于是你写下了 f(i,j)=f(i-1,j)。但是第 i 组还可以选择一个字符串转移，每个字符串都有转移的可能，于是你选择枚举这个组的所有字符串 s_k（1 \le k \le c_i）。显然，当一个字符串是 T 的后缀时可以转移。抛去这个后缀，前面的部分，也就是 T 的前 j-|s_k| 位，就由前 i - 1 组负责组成，这样才可以保证不重复，组成的代价就是 f(i-1,j-|s_k|)，而接上这个后缀本身还有 1 点代价。于是你写下了下面这条式子：

f(i,j)=\min\{f(i,j),f(i-1,j-|s_k|) + 1\}

当然，你知道这个转移只有在 s_k 是 T 的后缀时才可以进行。而你又考虑到 f(i,j)=f(i-1,j) 对于每个 j 都成立，因此你决定在转移前先复制一下 f(i-1) 到 f(i)，这样子就只用考虑第二种转移了。

现在你苦于怎么判断后缀，这个时候你突然想起了 substr，你只需要通过它取出最后 |s_k| 位，然后再来看看是否与 s_k 一样就可以了。

你开始敲代码，敲的时候发现如果 |s_k|>j，那么显然转移不了，直接跳过即可，还有就是要初始化数组全部为无穷大，这样会方便求最小。当然，你也记得在初始化完后，将 f(0,0) 设置为 0，这样就可以正确地转移了。

最后，你成功地通过了此题。

\mathtt{Code}

#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
//#define endl '\n'
#define IL inline
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;

IL int read()
{
    int x = 0,f = 1;
    char c = getchar();
    while(c <'0'|| c >'9'){if(c == '-') f = -1;c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0',c = getchar();
    return x * f;
}

void write(int x)
{
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

int n, f[105][105], c[105];
string t, s[105][105];

int main()
{
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
    cin >> t;
    cin >> n;
    int m = t.size();
    for(int i = 1;i <= n;i++)
    {
        cin >> c[i];
        for(int j = 1;j <= c[i];j++)
        {
            cin >> s[i][j];
        }
    }
    memset(f, 0x7f, sizeof(f));
    f[0][0] = 0;
    for(int i = 1;i <= n;i++)
    {
        memcpy(f[i], f[i - 1], sizeof(f[i - 1]));
        for(int j = 1;j <= m;j++)
        {
            for(int k = 1;k <= c[i];k++)
            {
                int gft = s[i][k].size();
                if(gft > j) continue;
                if(t.substr(0, j).substr(j - gft) == s[i][k]) f[i][j] = min(f[i][j], f[i - 1][j - gft] + 1);
            }
        }
    }
    cout << (f[n][m] == 0x7f7f7f7f ? -1 : f[n][m]) << endl;
    return 0;
}