AT_abc344_d 题解

这篇具有很好参考价值的文章主要介绍了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文章来源地址https://www.toymoban.com/news/detail-837959.html

代码

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

到了这里,关于AT_abc344_d 题解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • [ABC318E] Sandwiches 题解

       给定包含 (n) 个整数的序列 (a) ,其中任意元素的值 (a_i in [1,n]) ,统计包含三个元素的满足以下条件有序三元组数量:满足下标严格递增;满足第一个和最后一个元素相等,而中间的元素和两端的元素不相等。    记录三元组 ((a_i,a_j,a_k)) ,即 (1 le i j k le n ,

    2024年02月10日
    浏览(40)
  • ABC330 A-E 题解

    枚举一遍,当前数大于 (L) 使 (ans+1) 即可. 枚举一遍,当前数在 (L,R) 之间,结果就是它本身,小于 (L) 为 (L) ,大于 (R) 为 (R) . 枚举 (i:0simsqrt{d}) 为第一个数,以 (1) 为左边界, (sqrt{d-i^2}+1) 为右边界,判定条件为 (mid^{2}) 与 (d-i^2) 之间的大小关系,每次更新边界后 (ans=

    2024年02月05日
    浏览(41)
  • ABC341A-D题解

    这个没什么好说的,就先输出一个 1 ,再输出 n n n 个 01 就大功告成了。 要获取更多 x x x 国货币,只能用 x − 1 x - 1 x − 1 国货币换。 所以我们可以从 1 1 1 国一直换到 n n n 国,输出,结束。 你会发现, 50 0 3 2 ⋅ 1 0 8 500^32cdot10^8 50 0 3 2 ⋅ 1 0 8 ,所以可以暴力枚举高桥所在

    2024年02月19日
    浏览(32)
  • 题解:ABC320B - Longest Palindrome

    链接:Atcoder。 链接:洛谷。 算法难度:C。 思维难度:C。 调码难度:C。 综合评价:入门。 字符串处理。 通过双层循环分别枚举第一个字符和最后一个字符遍历每个子串,在分别判断是否为回文串,在所有是回文串的里面取长度最大值。 O(|s|2)。 字符串截取用substr函数。

    2024年02月07日
    浏览(41)
  • [ABC347C] Ideal Holidays题解

    原题传送门 原题传送门(洛谷) ​题意翻译: ​在 (AtCoder) 王国中,一个周有 (A+B) 天。其中在一周中, ([1,A]) 天是假日, ([A+1,B]) 天是工作日。 ​高桥有 (N) 个计划,第 (i) 个计划安排在 (i) 天后。他不知道今天是周几,但他想知道是否能将计划都安排在假期中;

    2024年04月08日
    浏览(41)
  • [AGC055B] ABC Supremacy 题解

    给定两个长度为  (n)  的字符串  (a) , (b) 。 你可以进行若干次以下操作: 若  (a)  中的一个 子串 为  ABC , BCA  或  CAB ,那么可以将这个子串替换为  ABC , BCA  或  CAB 。 求能否将  (a)  变成  (b) ,输出  YES  或  NO 。 不难发现,我们可以根据一些变换将 A

    2024年02月08日
    浏览(35)
  • [AGC055A] ABC Identity 题解

    给定长度为 (3n (1 le n le 2e5)) 的序列,其中字母 A,B,C 各有 (n) 个。 一个合法序列 (T) 满足以下条件: 其长度为 (3k (1 le k le n)) 。 (T_1 = T_2 = ... = T_k) (T_{k + 1} = T_{k + 2} = ... = T_{2k}) (T_{2k + 1} = T_{2k + 2} = ... = T_{3k}) (T_1, T_{k + 1}, T_{2k + 1}) 互不相同。 求一个把这个序列分

    2024年02月08日
    浏览(46)
  • [ABC319E] Bus Stops 题解

      给定 (n) 个公交站。对于第 (i) 个公交站,在时刻 (p_i times k,k in mathbb{N}) 有一辆公交车出发,在经过 (t_i) 的时间后,到达第 (i+1) 个公交站。   在走到第一个公交车之前需要走 (X) 时刻,做到最后一个公交站之后下车以后还需要走 (Y) 时刻。   约束: (1

    2024年02月09日
    浏览(34)
  • [ABC318C] Blue Spring 题解

      主人公出去旅游要买票,共有若干天,每天要花不同钱。现在有“通行证”出售,通过购买通行证,可以在某一天直接用通行证,以此来省去当天原本需要花费的票价。通行证只能一套一套买,每套中有 (D) 个,买一套要花费 (P) 元。可以购买任意套数的通行证,求怎

    2024年02月10日
    浏览(40)
  • AtCoder abc336 A~D题解

    题目翻译: 对于正整数 X X X 级别的龙串, X X X 是长度为 ( X + 3 ) (X+3) ( X + 3 ) 的字符串,由按此顺序排列的 o 、 n 和 g 的一次 L 、 X X X 次出现形成。 你得到一个正整数 N N N 。打印 N N N 级的龙串。 分析 按题目要求做即可……,输出一个 L ,循环 X X X 次输出 o ,再输出 ng 。

    2024年01月15日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包