Codeforces 1841C Ranom Numbers

题目来自 Codeforces Educational Round #150 (Div.2) C。link

  This article provides a feasible solution to a certain competitive programming problem.   If you have better solutions, feel free to share with me!

Problem Description

定义 \(A=1, B=10, C=100, D=1000, E=10000\)，输入一个只包含 \(A-E\) 的字符串 \(s\)。

我们定义 \(s\) 中某个字符 \(s_i\) 的价值 \(v_i\) 为：

• 存在 \(j>i\) 使得 \(s_j>s_i\)，则 \(v_i\) 为 \(s_i\) 所对应数字的相反数
• Otherwise，\(v_i\) 为 \(s_i\) 所对应的数字

定义字符串 \(s\) 的价值为其中所有字符价值之和 \(\sum v_i\)，你可以修改至多一个字符，使得修改过后的字符串 \(s'\) 的价值最大，并求出该最大值。\(1\leq |s|\leq 2\times10^5, 1\leq t\leq 10^4\)。

Tutorial

虽然最后顺着考试时的思路做出来了，但是非常的丑陋，代码就不放在这里贻笑大方了。思路很简单：枚举每一个 \(s_i\) ，计算将其分别改成 \(A-E\) 时对答案造成的影响并取最大值。然而这样做需要分类讨论，代码十分的 lengthy 且 error-prone。因此不仅时间复杂度是堪堪可过的 \(O(\)大常数 \(5n)\)，实现起来也让人晕头转向。

Greedy Approach

这道题的贪心做法认为，对于某个字母，如果我们要将其改大，那么修改其第一次出现 (first occurance) 的位置最优；如果我们要将其改小，那么修改其最后一次出现 (last occurance) 的位置最优。证明见 editorial。如此，一共只有 \(5\times 2\) 个位置需要考虑。枚举每个位置改变的字母并 \(O(n)\) 计算答案，时间复杂度为 \(O(50n)\)。

虽然这个贪心看上去很妙，但是我有一个地方没想通，题解中的证明也没有考虑到这种情况：例如对于 \(CEC\) ，若我们要将 \(C\) 改大成 \(D\)，按照贪心的思路，应该将第一个 \(C\) 改为 \(D\)。然而实际上将第二个 \(C\) 改为 \(D\) 最优。这一特例影响了证明的正确性，我也无法找到合适的解释，所以在此就不采用贪心实现了。

DP Approach

字符串中每一个字母的值受其右侧的最大字母影响；为了方便进行 DP，我们将字符串翻转，字母的值转而受到其左侧的最大字母影响。

令 \(dp[i][j][k]\) 表示考虑到第 \(i\) 个字符，前 \([0,i]\) 个字符中最大的字符为 \(j\)，前 \([0,i]\) 个字符中是否 \((k=0/1)\) 发生了改变，在该状态下字符串的最大值。转移很简单：对于状态 \(dp[i][j][k]\)，若 \(k=0\)，我们枚举 \(j\) 并由 \(dp[i-1][j][0]\) 进行转移。若 \(k=1\)，我们考虑被修改的字母位于 \([1,i-1]\) 还是就处在当前位置 \(i\)。第一种情况与 \(k=0\) 的转移类似，而第二种情况，我们进行二层枚举，枚举当前位置修改过后的字母并由 \(dp[i-1][j][0]\) 进行转移。

Code Implementation

这里的代码实现采用的思路是 DP。

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

const int MAX_N = 2e5 + 10;
const int inf = 1e9 + 10;

const int num[5] = {1, 10, 100, 1000, 10000};

int dp[MAX_N][5][2];

int main() {

    int t;
    cin >> t;
    while (t--) {
        string rev_s, s = "/";
        cin >> rev_s;
        int len = rev_s.length();
        for (int i = len - 1; i >= 0; --i)  s += rev_s[i];

        for (int i = 1; i <= len; ++i)
            for (int j = 0; j < 5; ++j)
                for (int k = 0; k <= 1; ++k)    dp[i][j][k] = -inf;

        dp[1][s[1] - 'A'][0] = num[s[1] - 'A'];    // initiate if i = 1
        for (int j = 0; j < 5; ++j) {
            if (j == s[1] - 'A')    continue;
            dp[1][j][1] = num[j];
        }

        for (int i = 2; i <= len; ++i) {
            int now = s[i] - 'A';
            for (int j = 0; j < 5; ++j) {
                int mx_j = max(now, j);
                dp[i][mx_j][0] = max(dp[i][mx_j][0], 
                                     dp[i - 1][j][0] + (j > now ? -num[now] : num[now])); 
                dp[i][mx_j][1] = max(dp[i][mx_j][1], 
                                     dp[i - 1][j][1] + (j > now ? -num[now] : num[now]));
            }
            for (int j = 0; j < 5; ++j) {
                for (int k = 0; k < 5; ++k) {
                    if (k == now)   continue;
                    int mx_j = max(k, j);
                    dp[i][mx_j][1] = max(dp[i][mx_j][1], 
                                         dp[i - 1][j][0] + (j > k ? -num[k] : num[k]));
                }
            }
        }

        int ans = -inf;
        for (int j = 0; j < 5; ++j)
            ans = max(ans, max(dp[len][j][1], dp[len][j][0]));
        
        cout << ans << endl;
    }

    return 0;
}