题解 | #小苯的ovo2.0#

1. 问题分析

题目要求通过将字符串 $S$ 中的 '??' 替换为 'o' 或 'v'，以最大化目标子序列的个数。首先，根据示例数据的推演，我们需要纠正一个关键逻辑点：

数学特征：对于一个确定的字符串，其 "ovo" 子序列的总数可以通过遍历所有字符 'v' 并计算其左右两侧 'o' 的数量乘积来获得。设最终字符串中 'o' 的总个数为 $N_o$ ，在位置 $i$ 处的字符为 'v'，且其左侧有 $pre\_o[i]$ 个 'o'，则该 'v' 对答案的贡献为： $Contribution(v_i) = pre\_o[i] \times (N_o - pre\_o[i])$ 总数量为： $\sum_{i: S[i]='v'} pre\_o[i] \times (N_o - pre\_o[i])$ 。

2. 算法：动态规划

由于每个 '?' 的决策（变 'o' 还是 'v') 会影响全局的 $N_o$ 以及后续位置的 $pre\_o$ ，且决策之间存在依赖关系，此问题具有明显的最优子结构和重叠子问题性质。

难点分析：贡献函数 $f(x) = x(N_o - x)$ 依赖于全局变量 $N_o$ 。这意味着在进行局部决策时，如果不知道最终字符串中有多少个 'o'，我们就无法准确计算当前位置填入 'v' 的贡献。

对策：通过枚举全局状态（枚举法 + DP）。既然 $|S| \le 500$ ，我们可以枚举最终字符串中 'o' 的总数 $M$ （ $M$ 的范围是从“原有的 'o' 数量”到“原有的 'o' 加 '?' 的总数”）。一旦 $M$ 固定，每个位置的贡献计算式就变得确定。

第一阶段：枚举与初始化

统计字符串中已有的 'o' 的数量 $count\_o$ 和 '?' 的数量 $count\_?$ 。
初始化全局最大值 $ans = 0$ 。
遍历所有可能的 'o' 总数 $M$ ，其中 $M \in [count\_o, count\_o + count\_? ]$ 。

第二阶段：状态定义与转移（针对固定的 $M$ ）

对于每一个确定的 $M$ ，执行一次线性 DP：

状态定义： $dp[j]$ 表示当前已处理的字符中，包含 $j$ 个 'o' 时能获得的最大 "ovo" 子序列数量。
状态转移：
- 若当前字符 $S[i] == 'o'$ ：则必须作为 'o' 处理，当前 'o' 数量增加， $dp[j] = dp[j-1]$ （需逆向遍历 $j$ 以防止重复使用同一位置）。
- 若当前字符 $S[i] == 'v'$ ：则该位置产生贡献 $j \times (M - j)$ 。状态转移为： $dp[j] = dp[j] + j \times (M - j)$ 。
- 若当前字符 $S[i] == '?'$ ：面临分支决策：
  1. 填入 'o'：对应状态 $dp[j-1]$ 。
  2. 填入 'v'：对应状态 $dp[j] + j \times (M - j)$ 。取两者最大值： $dp[j] = \max(dp[j-1], dp[j] + j \times (M - j))$ 。

第三阶段：结果汇总

每次枚举完 $M$ 后，更新 $ans = \max(ans, dp[M])$ 。

3. 代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static constexpr ll INF = -2e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        string s;
        cin >> s;
        int n = s.length();
        int co = 0;
        int cx = 0;
        for (const char c : s) {
            if (c == 'o')
                co++;
            else if (c == '?')
                cx++;
        }

        ll ans = 0;

        for (int M = co; M <= co + cx; M++) {
            vector<ll> dp(M + 1, -1);
            dp[0] = 0;

            for (const char c : s) {
                if (c == 'o') {
                    for (int j = M; j >= 0; j--) {
                        if (j > 0 && dp[j - 1] != -1)
                            dp[j] = dp[j - 1];
                    }
                } else if (c == 'v') {
                    for (int j = M; j >= 0; j--) {
                        if (dp[j] != -1) {
                            dp[j] += (ll)j * (M - j);
                        }
                    }
                } else if (c == '?') {
                    for (int j = M; j >= 0; j--) {
                        ll res_v = -1;
                        ll res_o = -1;

                        if (dp[j] != -1) {
                            res_v = dp[j] + (ll)j * (M - j);
                        }
                        if (j > 0 && dp[j - 1] != -1) {
                            res_o = dp[j - 1];
                        }

                        dp[j] = max(res_v, res_o);
                    }
                }
                if (dp[M] != -1) {
                    ans = max(ans, dp[M]);
                }
            }
        }

        cout << ans << "\n";
    }
}

4. 复杂度分析

时间复杂度：
- 外层枚举 $M$ ：最多 $N$ 次（ $N = |S|$ ）。
- 内层遍历字符串： $N$ 次。
- 状态转移空间覆盖： $M$ 次（约 $N$ 次）。
- 总体复杂度为 $O(N^3)$ 。
空间复杂度：
- 由于使用了滚动数组（一维 DP 优化），空间复杂度为 $O(N)$ 。