Problem

给一个由问号和数字组成的数字串A（问号表示任一数字）。

再给定n个数字Bi，和0~9的数字的价值。

F（x）表示x各个位数上的价值和。问A为何值时，sum(F(Bi+A))的值最大为多少。

1 ≤ A,Bi < 101000 没有前导零

Solution

dp[i][j]表示第i位时有j个数发生进位时的最大值。

然后我们对有没有进位的情况进行分类讨论

Notice

每次做之前要radixsort一下

Code

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define rank t

#define sqz main

#define ll long long

#define reg register int

#define rep(i, a, b) for (reg i = a; i <= b; i++)

#define per(i, a, b) for (reg i = a; i >= b; i--)

#define travel(i, u) for (reg i = head[u]; i; i = edge[i].next)

const int INF = 1e9, N = 1000;

const double eps = 1e-6, phi = acos(-1);

ll mod(ll a, ll b) {if (a >= b || a < 0) a %= b; if (a < 0) a += b; return a;}

ll read(){ ll x = 0; int zf = 1; char ch; while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();

if (ch == '-') zf = -1, ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;}

void write(ll y) { if (y < 0) putchar('-'), y = -y; if (y > 9) write(y / 10); putchar(y % 10 + '0');}

int rank[N + 5], S[N + 5][N + 5], now[N + 5], num[10], F[N + 5][N + 5], len[N + 5], V[10];

char st[N + 5][N + 5];

int m;

void radixsort(int pos)

{

	memset(num, 0, sizeof num);

	rep(i, 1, m) num[S[i][pos]]++;

	per(i, 9, 1) num[i - 1] += num[i];

	per(i, m, 1) now[num[S[rank[i]][pos]]--] = rank[i];

	rep(i, 1, m) rank[i] = now[i];

}

int sqz()

{

	scanf("%s", st[0] + 1);

	int n = len[0] = strlen(st[0] + 1);

	m = read();

	rep(i, 1, m) scanf("%s", st[i] + 1), len[i] = strlen(st[i] + 1), n = max(n, len[i]);

	n++;

	rep(i, 0, m)

		rep(j, 1, len[i])

			S[i][j + n - len[i]] = (st[i][j] == '?' ? -1 : st[i][j] - '0');

	rep(i, 0, 9) V[i] = read();

	rep(i, 1, n)

		rep(j, 0, m) F[i][j] = -INF;

	int l = S[0][n] == -1 ? 0 : S[0][n], r = S[0][n] == -1 ? 9 : S[0][n];

	rep(i, l, r)

	{

		int cnt = 0, total = 0;

		rep(j, 1, m)

		{

			if (i + S[j][n] >= 10) cnt++;

			total += V[(i + S[j][n]) % 10];

		}

		F[n][cnt] = max(F[n][cnt], total);

	}

	rep(i, 1, m) rank[i] = i;

	rank[m + 1] = m + 1;

	per(i, n - 1, 1)

	{

		radixsort(i + 1);

		int l = S[0][i] == -1 ? 0 : S[0][i], r = S[0][i] == -1 ? 9 : S[0][i];

		if (n - i + 1 == len[0] && l == 0) l++;

		rep(num, l, r)

		{

			int cnt = 0, total = 0;

			rep(j, 1, m)

			{

				if (max(len[j], len[0]) < n - i + 1) continue;

				total += V[(S[j][i] + num) % 10];

				cnt += S[j][i] + num >= 10;

			}

			rep(j, 1, m + 1)

			{

				F[i][cnt] = max(F[i][cnt], F[i + 1][j - 1] + total);

				total += (max(len[rank[j]], len[0]) >= n - i + 1 || (S[rank[j]][i] + num + 1) ? V[(S[rank[j]][i] + num + 1) % 10] : 0) - (max(len[rank[j]], len[0]) >= n - i + 1 || (S[rank[j]][i] + num)? V[(S[rank[j]][i] + num) % 10] : 0);

				cnt += S[rank[j]][i] + num + 1 == 10;

			}

		}

	}

	int ans = 0;

	rep(i, 0, m) ans = max(ans, F[1][i]);

	printf("%d\n", ans);

	return 0;

}