算法
(部分列DP)
题意:统计字符串 $S$ 中有多少个标记不相邻的非空子列
若把原问题退化成标记可以相邻应该怎么做?
栗子:
abc
: 其中每个字符都不同,并且每个字符可取或可不取(类似于背包问题),显然有 $2^3 - 1$ 个非空子序列
ababc
:我们可以发现位置 $(1, 2), (1, 4), (3, 4)$ 处的字符都能构成 ab
,这里出现了重复计数,我们可以只保留下标字典序小的那一组,这样就能避免重复
下面引入一个叫做 部分列DP
的方法,可以完全避免重复计数
记 dp[i]
表示最后一个字符包含 $s[i]$ 的子列个数
转移方程为 $dp[i]=\sum\limits_{j = 0}^{i - 1} dp[j]$,这个显然会包含重复项,我们可以在 $0 \sim i - 1$ 中找到最大的 $k$,使得 $s[k] = s[i]$,然后把 $dp[0] \sim dp[k - 1]$ 剪掉即可,也就是 $dp[i] = \sum\limits_{j = k}^{i - 1} dp[j]$
这个想法同样可以应用到原题上。令 $dp[0] = 1, dp[1] = 0$,转移方程如下:
$dp[i + 1] = \sum\limits_{j = k}^{i - 1} dp[j]$
注意:
标记可以相邻的问题是在 $S$ 前多加了一个字符比如 X
,X
对应的 dp[0] = 1
,答案是 $\sum\limits_{i = 1}^n dp[i]$
标记不相邻的问题是在 $S$ 前多加两个字符如 XY
,X
对应的 dp[0] = 1
,Y
对应的 dp[1] = 0
,答案是 $\sum\limits_{i = 2}^{n + 1} dp[i]$
C++ 代码
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::string;
using std::vector;
using mint = modint1000000007;
int main() {
string s;
cin >> s;
int n = s.size();
vector<mint> dp(n + 2);
dp[0] = 1;
mint ans;
rep(i, n) {
for (int j = i; j >= 0; --j) {
dp[i + 2] += dp[j];
if (j and s[j - 1] == s[i]) break;
}
ans += dp[i + 2];
}
cout << ans.val() << '\n';
return 0;
}
#include <atcoder/all>
这玩意是啥 qwqand可太强了
bits/stdc++.h
带俩宏定义#define and &&
#define or ||
我知道阿,上面那个是acl(AtCoder Liberary
有啥用
https://www.cnblogs.com/RioTian/p/14579327.html 呃呃自己慢慢看吧