AT_abc344_d 题解
Vocaloid世末歌者
·
·
题解
本文同步发表于 cnblogs。
赌狗天天输的一集。
大意
你最开始有一个空字符串 S。
你还有编号为 1, 2, \dots, N 的袋子，每个袋子都包含一些字符串。
袋子 i 包含 A_i 个字符串 S_{i,1}, S_{i,2}, \dots, S_{i,A_i}。
对 i = 1, 2, \dots, N 重复以下步骤仅一次（这里原题没有讲清楚）：
- 执行以下两个操作之一：
- 支付 1 日元，从袋子 i 中选择一个字符串，并将其接到 S 的末尾。
- 睡觉（啥都不干）。
给定一个字符串 T，求使最后 S 等于 T 所需的最小金额。
如果无法使最后的 S 等于 T，则打印 -1。
思路
我最开始打了个爆搜，众所周知寄了。
然后疯狂推 DP，一阵木大木大后我开窍了：
用 dp_{i,j} 表示处理到了第 i 个袋子，现在这个字符串已经有 j 位（而且与 t 匹配）了。
初始化所有位置为无穷大（比如说我取的一千多，够了）。
首先枚举每个袋子。
然后肯定是要 dp[i][j]=dp[i-1][j] 的（万一你这组没出息你要保留实力）
然后你枚举一下袋子里的哪个字符串，再枚举一下 k（加上这个字符串之前的长度）。
如果加上这个字符串后能与 t 匹配，dp[i][k+s[i][j].size()-1]=min(dp[i][k+s[i][j].size()-1],dp[i-1][k-1]+1);。注意我的代码是从 1 开始的。
最后看一下 dp[n][t.size()]，如果不是无穷大，就输出它，否则就输出 -1。
Posted on cnblogs too. But I didn't write English solution there.
I'm a big fool.
Solution
I used DFS at first, and got TLE.
Then I started to think about DP:
Initialization the whole $dp$ array to infinity.
Then enumerate the bags.
Remember to `dp[i][j]=dp[i-1][j]` at first.
And then enumerate the strings in this bag, then $k$（$k$ means the lenth of the string before adding this string）.
If after adding this string the whole string can match with $t$, `dp[i][k+s[i][j].size()-1]=min(dp[i][k+s[i][j].size()-1],dp[i-1][k-1]+1);` to update.
Print `dp[n][t.size()]` at last. Of course, if `dp[n][t.size()]` equals to infinity, printf $-1$ instead.
### 代码/code
```cpp
#include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 LL
#define lowbit(x) ((x)&(-(x)))
#define lc (u<<1)
#define rc (u<<1|1)
using namespace std;
void read(i128 &x)
{
i128 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*10+ch-'0';
ch=getchar();
}
x*=f;
}
void write(i128 x)
{
if(x>=10)write(x/10);
putchar(x%10+'0');
}
LL n,a[110],dp[110][110];
string t,s[110][20];
int main()
{
cin>>t>>n;
rep(i,0,n,1)rep(j,1,t.size(),1)dp[i][j]=1029;
rep(i,1,n,1)
{
cin>>a[i];
rep(j,1,a[i],1)cin>>s[i][j];
}
rep(i,1,n,1)
{
rep(j,0,t.size(),1)dp[i][j]=dp[i-1][j];
rep(j,1,a[i],1)
{
for(LL k=1;k+s[i][j].size()-1<=t.size();k++)
{
bool f=1;
rep(l,1,s[i][j].size(),1)
{
if(s[i][j][l-1]!=t[k+l-2])
{
f=0;
break;
}
}
if(f)
{
dp[i][k+s[i][j].size()-1]=min(dp[i][k+s[i][j].size()-1],dp[i-1][k-1]+1);
}
}
}
}
if(dp[n][t.size()]==1029)cout<<-1<<endl;
else cout<<dp[n][t.size()]<<endl;
return 0;
}
```