#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const ll inf = 1e12;

int c, t;
int cnt[10], d[10];
int nxt[N][10];
string n;
ll v[10], dp[N];

void init() {
    for (ll i = 1; i <= 9; i++) dp[i] = min(i, v[i]), cnt[i] = 0;
    for (int i = n.length() - 1; i >= 0; i--) 
    	for (int j = 1; j <= 9; j++) 
			nxt[i][j] = -1;
	
    for (int Homura = 11; Homura < N - 5; Homura++) {
        int j = 10;
        dp[Homura] = Homura;
        while (j < Homura) {
            dp[Homura] = min(dp[Homura], dp[(Homura / j) * (j / 10) + (Homura % (j / 10))] + v[(Homura % j) / (j / 10)]);
            j *= 10;
        }
    }
}

bool check(int x) {
	int j = 100000;
	while (j > x) j /= 10;
	int temp = x;
	while (temp) {
		if (temp % 10 == 0) return 0;
		temp /= 10;
	}
	if (x == j && j > 1) return 0;
	int id = -1;
	while (j) {
		id = nxt[id + 1][x / j];
		if (id == -1) return 0;
		x = x % j;
		j /= 10;
	}
	return 1;
}

int main() {
    ios::sync_with_stdio(0);
    cin >> c >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= 9; i++) cin >> v[i];
        init();
        if (n.length() <= 5) {
            int ans = 0;
            for (int i = 0; i < n.length(); i++) ans = ans * 10 + n[i] - '0';
            cout << dp[ans];
        }
        else {
        	ll ans = 1e18;
        	for (int i = n.length() - 1; i >= 0; i--) {
				cnt[n[i] - '0']++;
        		for (int j = 1; j <= 9; j++) {
        			if (n[i] - '0' == j) nxt[i][j] = i;
        			else nxt[i][j] = nxt[i + 1][j];
				}
			}
			for (int i = 10001; i < N - 5; i++) {
				if (check(i)) {
					for (int j = 1; j <= 9; j++) d[j] = 0;
					int temp = i;
					while (temp) {
						d[temp % 10]++;
						temp /= 10;
					}
					ll sum = dp[i];
					for (int j = 1; j <= 9; j++) sum += (cnt[j] - d[j]) * v[j];
					ans = min(ans, sum);
				}
			}
			cout << ans;
        }
        cout << endl;
    }
    return 0;
}

我的想法是预处理出1~ 10^5的所有最小值，然后暴力查询每一个合法的剩余序列。

评测记录

话说怎么过了14~25没过前面的点