本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-12 20:25:36

题目
正解：dp。
歪解：枚举，剪枝。（这告诉我们暴力出奇迹）

我们可以开一个 vector，第一个值是拼成的字符串，第二个值是支付的日元数，然后存储所有的可能，但时间空间根本不允许。
那么我们可以考虑剪枝，当以下情况满足一种的时候，字符串就不用存储：

1. 字符串出现过且之前的最少日元数比现在少；
2. 该字符串不等于对于任何一个 $x$ 的 $T_{1\dots x}$。

剩下就没了，但需要注意：在每个袋子里最多选一个！
代码：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define INF 214748364721474836
using namespace std;
inl int read(){
    int f=1, x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return f*x;
}
inl void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>=10) write(x\/10);
    putchar(x%10^48);
    return;
}
#define N 105
#define A 15
string t,s[N][A];
int n,a[N],ans=INF;
vector<pair<string,int> >g;
map<string,int>mp;
inl bool cstrstr(string a,string b){
	for(int i=0;i<a.size();++i)
		if(a[i]!=b[i]) return false;
	return true;
}
signed main(){
	cin>>t;
	n=read();
	g.push_back({"",0});
	for(int i=1;i<=n;++i){
		a[i]=read();
		for(int j=1;j<=a[i];++j) cin>>s[i][j];
	}
	for(int i=1;i<=n;++i){
		int siz=g.size();
		string str="";
		for(int j=1;j<=a[i];++j)
			for(int k=0;k<siz;++k){
				str=g[k].first+s[i][j];
				if(str.size()<=t.size()&&(!mp[str]||mp[str]>g[k].second+1)&&cstrstr(str,t)){
					g.push_back({str,g[k].second+1});
					mp[str]=g[k].second+1;
				}
			}
	}
	for(int i=0;i<g.size();++i)
		if(g[i].first==t) ans=min(ans,g[i].second);
	if(ans==INF) puts("-1");
	else write(ans);
    return 0;
}