题目传送门

分享一下我做这道题是的心路历程。

首先感觉像是贪心，但是随便举了几个例子就推翻了，发现无论是先删掉 \(v\) 值小的，还是先删掉靠前且数值大的都不行。

策略的选择如此复杂，考虑 dp。

其实很容易就能发现数据范围的异样：\(v_i\le 10^5\)，这告诉我们操作 \(2\) 最多只能操作最后的 \(5\) 个数。

因为 \(5\times 10^5>10^5\)，而 \(6\times 10^5<10^6\)，所以选超过 \(5\) 个数进行操作二一定不如操作一优。

自此，我们可以将题意转化为：

给定一个序列 \(s\)，从 \(s\) 中选出一个子序列 \(\{a_1, a_2,\cdots,a_k\}\)，使得 \(\overline{a_1a_2\cdots a_k} - \sum\limits_{i = 1}^kv_i\) 最小。

dp 的状态设计其实可以参考数据范围，设 \(n\) 为原数的长度，考虑状态设计为 \(dp_{i, j}\)。

一开始我想的是直接线性 dp，从前向后递推，同时记录下此时最优策略保留下来的数来辅助递推，但很快就发现连样例 \(2\) 的第一组数据都过不了。

错误 \(\texttt{Code:}\)

#include <cstring>
#include <iostream>

#define x first
#define y second

using namespace std;

const int N = 100010;
typedef long long ll;
typedef pair<ll, ll> PLL;
int cid, T;
int n;
char s[N];
int v[10];
PLL dp[N][6];

void solve() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for(int i = 1; i < 10; i++) scanf("%d", &v[i]);
    ll sumcost = 0;
    for(int i = 1; i <= n; i++)
        sumcost += v[s[i] - '0'];
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= 5; j++)
            dp[i][j] = {1e18, 0};
    dp[0][0] = {0, 0};
    for(int i = 1; i <= n; i++) {
        int limit = min(i, 5);
        dp[i][0] = dp[i - 1][0];
        for(int j = 1; j <= limit; j++) {
            dp[i][j] = dp[i - 1][j];
            if(dp[i][j].x > dp[i - 1][j - 1].x + dp[i - 1][j - 1].y * 10 + s[i] - '0' - v[s[i] - '0'])
                dp[i][j] = {dp[i - 1][j - 1].x + dp[i - 1][j - 1].y * 10 + s[i] - '0' - v[s[i] - '0'], dp[i - 1][j - 1].y * 10 + s[i] - '0'};
        }
    }
    ll ans = 1e18;
    for(int i = 0; i <= min(5, n); i++)
        ans = min(ans, dp[n][i].x);
    printf("%lld\n", sumcost + ans);
}

int main() {
    scanf("%d%d", &cid, &T);
    while(T--) {
        solve();
    }
    return 0;
}

然后我就发现：正着 dp 是错的。

因为你正着 dp 的时候只会保留当前长度下最优的解，但它实际上是具有后效性的。

就是这组样例：

3158927982863528
41423 65081 37768 31661 5606 86055 71796 46535 92370

最优的策略是保留 \(19796\) 最后删，其余全用方法一删掉。

但如果正着这样 dp，那么当考虑前 \(8\) 位时，最优解是删掉 \(9796\)，而删掉 \(1979\) 这个策略的就被覆盖掉了。但事实上最后用后者更新的答案是要比前者更优的。

但是倒着 dp 就没有后效性了！

原因就是如果倒着做，每次更新时直接加上 \(num_i\times 10^{j - 1}\) 再减去 \(v_{num_i}\) 就行了，各个贡献的计算是独立进行的。

那么新的状态定于就是：\(dp_{i, j}\) 表示从后往前考虑到第 \(i\) 位时，保留了 \(j\) 个数时的最小 \(num - \sum v\)。

状态转移方程：

\(dp_{i, j} = \min\{dp_{i + 1, j}, dp_{i + 1, j - 1} + num_i\times 10^{j - 1} - v_{num_i}\}\)

最后答案就是选取 \(0\sim 5\) 个留下来的最小值，加上全用方法一消除的代价。

\(\texttt{AC Code:}\)

#include <cstring>
#include <iostream>

#define x first
#define y second

using namespace std;

const int N = 100010;
typedef long long ll;
int cid, T;
int n;
char s[N];
int v[10];
ll dp[N][6];
int power10[10];

void solve() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for(int i = 1; i < 10; i++) scanf("%d", &v[i]);
    ll sumcost = 0;
    for(int i = 1; i <= n; i++)
        sumcost += v[s[i] - '0'];
    for(int i = 0; i <= n + 1; i++)
        for(int j = 0; j <= 5; j++)
            dp[i][j] = 1e18;
    dp[n + 1][0] = 0;
    for(int i = n; i; i--) {
        dp[i][0] = dp[i + 1][0];
        int limit = min(5, n - i + 1);
        for(int j = 1; j <= limit; j++) {
            dp[i][j] = dp[i + 1][j];
            dp[i][j] = min(dp[i][j], dp[i + 1][j - 1] + (s[i] - '0') * power10[j - 1] - v[s[i] - '0']);
        }
    }
    ll ans = 1e18;
    for(int i = 0; i <= min(5, n); i++)
        ans = min(ans, dp[1][i]);
    printf("%lld\n", sumcost + ans);
}

int main() {
    scanf("%d%d", &cid, &T);
    power10[0] = 1;
    for(int i = 1; i < 10; i++)
        power10[i] = power10[i - 1] * 10;
    while(T--) {
        solve();
    }
    return 0;
}