10. We Love ABC

本文主要是介绍10. We Love ABC，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：We Love ABC

给一个只含 A B C ? 四种字符的串，其中 ? 可以匹配任意字母，问能形成多少个子序列 ABC。

先不考虑问号，在只有字母的情况下很容易想到动态规划：$dp[i][j]$ 表示前 $i$ 个字符形成长度为 $j$ 的子序列，直接从 $i-1$ 转移就行了。然后考虑问号的影响，问号相当于三种字母随便填，所以即便问号这一位不用于答案的子序列中，也会使上一个状态的贡献翻上三倍；如果这一位在子序列里用到了，那就相当于三种字母各转移一次。在之前的 dp 上稍作修改即可。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e5 + 5;
const ll mod = 1e9 + 7;
ll dp[maxn][4];
char s[maxn];
int main() {cin >> (s + 1);int n = strlen(s + 1);dp[0][0] = 1;for (int i = 1; i <= n; ++i) {if (s[i] == '?') {for (int j = 0; j <= 3; ++j)dp[i][j] = dp[i - 1][j] * 3 % mod;dp[i][1] = (dp[i][1] + dp[i - 1][0]) % mod;dp[i][2] = (dp[i][2] + dp[i - 1][1]) % mod;dp[i][3] = (dp[i][3] + dp[i - 1][2]) % mod;} else {for (int j = 0; j <= 3; ++j)dp[i][j] = dp[i - 1][j];if (s[i] == 'A') dp[i][1] = (dp[i][1] + dp[i - 1][0]) % mod;else if (s[i] == 'B') dp[i][2] = (dp[i][2] + dp[i - 1][1]) % mod;else dp[i][3] = (dp[i][3] + dp[i - 1][2]) % mod;}}cout << dp[n][3] << endl;return 0;
}

这篇关于10. We Love ABC的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---