ABC264 G - String Fair
2022/9/7 23:26:41
本文主要是介绍ABC264 G - String Fair,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
DP + 最短路 + 哈希
G - String Fair (atcoder.jp)
题意
给若干个只包含小写字母的长度<=3 的字符串 \(T_i\),每个字符串有权值
构造一个非空字符串 S,若 S 中包含上述子串,则加上这个子串的权值,求 S 的最大权值和
思路
由于 \(T_i\) 的长度不超过 3,所以对于当前的 S,若向后面再加一个字符 ch,则 ch 的贡献只与 S 中最后两个字符有关
因此可以把任意长度为2的字符串当作状态(也是图上的点),枚举再加一个字符,进行转移
即 若当前状态为 ab, 加了一个字符 c, 状态变为 bc,并且加了 c,bc,abc 的权值
问题转化为共有 26 * 26 个点,每个点可向外连 26 条边,边权为 c,bc,abc 的权值和,求最长路
用 floyd 或 spfa 即可,判正环可再做一次,如果某个点的最长路还能被更新,则有正环
用哈希处理字符串可更方便一些,具体见代码
#include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <cmath> using namespace std; #define endl "\n" typedef long long ll; typedef pair<int, int> PII; const ll INF = 1e18; const int N1 = 26, N2 = 26 * 26, N3 = 26 * 26 * 26, M = 26; int n; vector<ll> p1(N1), p2(N2), p3(N3); ll dist[N2]; int hs(string &s) { int ans = 0; for (auto i : s) { ans *= M; ans += i - 'a'; } return ans; } ll floyd() { for (int k = 0; k < N2; k++) { for (int i = 0; i < N2; i++) { for (int j = 0; j < N1; j++) { int now = i % M * M + j; ll now_dist = dist[i] + p1[j] + p2[now] + p3[i * M + j]; if (dist[now] < now_dist) dist[now] = now_dist; } } } for (int k = 0; k < N2; k++) { for (int i = 0; i < N2; i++) { for (int j = 0; j < N1; j++) { int now = i % M * M + j; ll now_dist = dist[i] + p1[j] + p2[now] + p3[i * M + j]; if (dist[now] < now_dist) return INF; } } } ll ans = *max_element(p1.begin(), p1.end()); for (int i = 0; i < N2; i++) ans = max(ans, dist[i]); return ans; } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> n; for (int i = 1; i <= n; i++) { string s; ll t; cin >> s >> t; int h = hs(s); if (s.size() == 1) p1[h] = t; else if (s.size() == 2) p2[h] = t; else p3[h] = t; } for (int i = 0; i < N2; i++) dist[i] = p2[i] + p1[i/M] + p1[i%M]; ll ans = floyd(); if (ans == INF) cout << "Infinity" << endl; else cout << ans << endl; return 0; }
这篇关于ABC264 G - String Fair的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-23增量更新怎么做?-icode9专业技术文章分享
- 2024-11-23压缩包加密方案有哪些?-icode9专业技术文章分享
- 2024-11-23用shell怎么写一个开机时自动同步远程仓库的代码?-icode9专业技术文章分享
- 2024-11-23webman可以同步自己的仓库吗?-icode9专业技术文章分享
- 2024-11-23在 Webman 中怎么判断是否有某命令进程正在运行?-icode9专业技术文章分享
- 2024-11-23如何重置new Swiper?-icode9专业技术文章分享
- 2024-11-23oss直传有什么好处?-icode9专业技术文章分享
- 2024-11-23如何将oss直传封装成一个组件在其他页面调用时都可以使用?-icode9专业技术文章分享
- 2024-11-23怎么使用laravel 11在代码里获取路由列表?-icode9专业技术文章分享
- 2024-11-22怎么实现ansible playbook 备份代码中命名包含时间戳功能?-icode9专业技术文章分享