题目传送门
分享一下我做这道题是的心路历程。
首先感觉像是贪心，但是随便举了几个例子就推翻了，发现无论是先删掉 \(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;
}