ToB企服应用市场:ToB评测及商务社交产业平台

标题: AT_abc344_d 题解 [打印本页]

---

作者: 钜形不锈钢水箱    时间: 2024-5-13 13:32
标题: 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[j]=dp[i-1][j] 的（万一你这组没前程你要保留实力）
然后你枚举一下袋子里的哪个字符串，再枚举一下 \(k\)（加上这个字符串之前的长度）。
如果加上这个字符串后能与 \(t\) 匹配，dp[k+s[j].size()-1]=min(dp[k+s[j].size()-1],dp[i-1][k-1]+1);。留意我的代码是从 \(1\) 开始的。
最后看一下 dp[n][t.size()]，如果不是无穷大，就输出它，否则就输出 -1。
代码

[code]#include#include#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 repn(i,a,b,g) for(LL i=a;ib;i-=g)#define pll pair#define mkp(x,y) make_pair(x,y)#define i128 LL#define lowbit(x) ((x)&(-(x)))#define lc (u>n;        rep(i,0,n,1)rep(j,1,t.size(),1)dp[j]=1029;        rep(i,1,n,1)        {                cin>>a;                rep(j,1,a,1)cin>>s[j];        }        rep(i,1,n,1)        {                rep(j,0,t.size(),1)dp[j]=dp[i-1][j];                rep(j,1,a,1)                {                        for(LL k=1;k+s[j].size()-1

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4