划分型dp+lcp优化,CF 611D - New Year and Ancient Prophecy
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
611D - New Year and Ancient Prophecy
二、解题报告
1、思路分析
一眼划分型dp,考虑如何定义状态
由于我们要能够进行字符串间的比较,所以我们这样定义状态:
f(i, j) 代表以s(j, i)结尾的合法划分数
那么如何转移?
上一个紧挨的字符串以s[j - 1]结尾
那么所有以s[j - 1]结尾且长度小于j - i + 1的划分都可以转移,这部分直接前缀和
我们只需判断s[2j - i - 1, j - 1]和s[j, i]的大小来决定f(j - 1, 2j - i - 1)是否可以转移
暴力比较是O(N)的,状态数有O(N^2),会超时
我们考虑如何O(1)比较
事实上,我们只需预处理lcp[i][j],代表i 和 j开头的最长公共前缀就可以快速判断了,预处理是O(N^2)的
2、复杂度
时间复杂度: O(N^2)空间复杂度:O(N^2)
3、代码详解
#include <bits/stdc++.h>
using i64 = long long;
using i128 = __int128;
using PII = std::pair<int, int>;
using PIII = std::pair<int, PII>;
const int inf = 1e9 + 7, P = 1e9 + 7;
void solve() {
int n;
std::cin >> n;
std::string s;
std::cin >> s;
std::vector<std::vector<int>> lcp(n + 2, std::vector<int>(n + 2)), f(lcp);
std::vector<std::vector<i64>> sum(n + 1, std::vector<i64>(n + 1));
for(int i = n; i; -- i) {
f[i][1] = 1;
for(int j = n; j; -- j)
if(s[i - 1] == s[j - 1])
lcp[i][j] = lcp[i + 1][j + 1] + 1;
}
auto check = [&](int i, int j) -> bool {
if (lcp[i][j] >= j - i) return false;
return s[i + lcp[i][j] - 1] < s[j + lcp[i][j] - 1];
};
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= i; ++ j) {
if (s[j - 1] ^ 48) {
int k = std::max(2 * j - i, 1);
f[i][j] = (((sum[j - 1][j - 1] - sum[j - 1][k - 1] + f[i][j]) % P) + P) % P;
-- k; // 等长的情况
if (k && check(k, j))
f[i][j] = (f[i][j] + f[j - 1][k]) % P;
}
sum[i][j] = (f[i][j] + sum[i][j - 1]) % P;
}
}
int res = 0;
for (int i = 1; i <= n; ++ i)
res = (1LL * res + f[n][i]) % P;
std::cout << res;
}
int main(int argc, char** argv) {
std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
int _ = 1;
// std::cin >> _;
while (_ --)
solve();
return 0;
}
原文地址:https://blog.csdn.net/EQUINOX1/article/details/140357361
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!