CF778E

和 CF1188D 是差不多的。

设 \(f_{i,j}\) 表示前 \(i-1\) 位，有 \(j\) 个数对第 \(i\) 位进了位时的最大答案。

进位的一定是后 \(i\) 位最大的一些数，直接利用上一次的排序结果再在前面添加一个数进行对一段后缀排序。

转移就枚举 \(A\) 当前这一位填什么。

具体细节看代码（参考了神 zhoukangyang 的）。

Code：

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

void chkmax(int &a, int b) { if (a < b) a = b; }

const int N = 1005;
string s[N], now;
int n, len[N], Len;
int w[N];
int f[N][N], hz[N], hv[N];
int p[N], D[N], arr[N], tot;

bool cmp(int x, int y) { return D[x] > D[y]; }

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> now >> n, Len = now.size(), reverse(now.begin(), now.end());
	for (int i = 1; i <= n; ++i) cin >> s[i], len[i] = s[i].size(), reverse(s[i].begin(), s[i].end()), p[i] = i;
	for (int i = 0; i < 10; ++i) cin >> w[i];
	for (int i = 1; i <= n; ++i) D[i] = 1;
	memset(f, -0x3f, sizeof f); f[0][0] = 0;
	for (int i = 0; i <= 1000; ++i) {
		if (i) {
			tot = 0;
			for (int j = 1; j <= n; ++j) if (len[j] >= i) D[j] += (s[j][i - 1] - '0') * (n + 1);
			for (int j = 1; j <= n; ++j) arr[++tot] = D[j];
			sort(arr + 1, arr + tot + 1), tot = unique(arr + 1, arr + tot + 1) - (arr + 1);
			for (int j = 1; j <= n; ++j) D[j] = lower_bound(arr + 1, arr + tot + 1, D[j]) - arr;
			sort(p + 1, p + n + 1, cmp);
		}
		int l = (i == Len - 1), r = 9;
		if (Len <= i) l = r = 0;
		else if (now[i] != '?') l = r = now[i] - '0';
		for (int d = l; d <= r; ++d) {
			int cur = 0, W = 0;
			for (int j = n; j; --j) {
				int v = (i > len[p[j]] - 1 ? 0 : s[p[j]][i] - '0');
				hv[j] = hv[j + 1], hz[j] = hz[j + 1];
				if (v + d || i < max(len[p[j]], Len)) hv[j] += w[(v + d) % 10], hz[j] += (v + d) / 10;
			}
			for (int j = 0; j <= n; ++j) {
				if (j) {
					int v = (i > len[p[j]] - 1 ? 0 : s[p[j]][i] - '0');
					W += w[(v + d + 1) % 10];
					cur += (v + d + 1) / 10;
				}
				chkmax(f[i + 1][cur + hz[j + 1]], f[i][j] + W + hv[j + 1]);
			}
		}
	}
	cout << f[1001][0];
	return 0;
}

原文地址：http://www.cnblogs.com/Kobe303/p/16796082.html