Codeforces Round #820 (Div. 3) G(字符串 + dp)
2022/9/15 23:18:40
本文主要是介绍Codeforces Round #820 (Div. 3) G(字符串 + dp),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Codeforces Round #820 (Div. 3) (字符串 + dp)
题意
两个字符串,一个原串,一个模板串。将原串中所有模板串的最小次数和所有方案数是多少。数据量 \(500\)
思路
考虑对原串中每一个出现的模板串dp。
定义 \(dp[i]\) 表示删除前 \(i\) 个模板串且最后删了 \(i\) 的最小操作次数。
转移做分类讨论。对于状态 \(i\) 如果前取 \(j\) 没有重叠,那么 \(i\) 和 \(j\) 无关,有+1的增量。如果重叠,删除了 \(i\) 一定不优。
另外如果不重叠状态 \(i\) 和 \(i\) 之间还有另外一个不重叠状态 \(k\) 如果转移就会少算,此时也不发生转移。
最后答案就是和最后出现的模板串有重叠的所有状态取最小。
方案数在做上面dp时顺便求一下即可。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<set> #include<queue> #include<map> #include<stack> #include<string> #include<functional> #include<cassert> #include<random> #include<iomanip> #define yes puts("yes"); #define inf 0x3f3f3f3f #define ll long long #define linf 0x3f3f3f3f3f3f3f3fll #define ull unsigned long long #define endl '\n' #define int long long #define SZ(x) (int)x.size() #define rep(i,a,n) for(int i = a;i <= n;i++) #define dec(i,n,a) for(int i = n;i >= a;i--) using namespace std; mt19937 mrand(random_device{}()); int rnd(int x) { return mrand() % x;} using PII = array<int,2>; const int MAXN =10 + 2e5 ,mod=1e9 + 7; void solve() { string s,t; cin >> s >> t; vector<int> at{0}; int n = s.size(); s = '*' + s; rep(i,1,n) if(s.substr(i,SZ(t)) == t) at.emplace_back(i + SZ(t) - 1); vector<int> f(SZ(at) + 1,linf), g(SZ(at) + 1,0); f[0] = 0; g[0] = 1; rep(i,1,SZ(at) - 1) { int pos = -1; dec(j,i - 1,0) { // ababa ab[a]ba if(at[i] - at[j] < SZ(t)) continue; if(pos - SZ(t) + 1 > at[j]) break; if(f[i] > f[j] + 1) { f[i] = f[j] + 1; g[i] = g[j]; }else if(f[i] == f[j] + 1) { g[i] = (g[i] + g[j]) % mod; } if(pos == -1) pos = at[j]; } } int mn = linf, ans = 0; rep(i,0,SZ(at) - 1) { if(at.back() - at[i] < SZ(t)) mn = min(mn, f[i]); } rep(i,0,SZ(at) - 1) if(mn == f[i] and at.back() - at[i] < SZ(t)) ans = (ans + g[i]) % mod; cout << mn << " " << ans << endl; } signed main() { ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int T;cin>>T; while(T--) solve(); return 0; }
这篇关于Codeforces Round #820 (Div. 3) G(字符串 + dp)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-26怎么使用nsenter命令进入容器?-icode9专业技术文章分享
- 2024-12-26导入文件提示存在乱码,请确定使用的是UTF-8编码怎么解决?-icode9专业技术文章分享
- 2024-12-26csv文件怎么设置编码?-icode9专业技术文章分享
- 2024-12-25TypeScript基础知识详解
- 2024-12-25安卓NDK 是什么?-icode9专业技术文章分享
- 2024-12-25caddy 可以定义日志到 文件吗?-icode9专业技术文章分享
- 2024-12-25wordfence如何设置密码规则?-icode9专业技术文章分享
- 2024-12-25有哪些方法可以实现 DLL 文件路径的管理?-icode9专业技术文章分享
- 2024-12-25错误信息 "At least one element in the source array could not be cast down to the destination array-icode9专业技术文章分享
- 2024-12-25'flutter' 不是内部或外部命令,也不是可运行的程序 或批处理文件。错误信息提示什么意思?-icode9专业技术文章分享