AT_abc344_d 题解

赌狗天天输的一集。

大意

你最开始有一个空字符串 \(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

代码

#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;
}

热门相关:惊艳人生   盛华   第一强者   士子风流   混在三国当军阀