自动搬运

查看原文

来自洛谷，原作者为

	cff_0102 & aqua_qaq | 团子群 185800038 | 如果我死了说明我 AFO 了

搬运于2025-08-24 23:05:05，当前版本为作者最后更新于2024-10-14 07:56:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

假设我们只做操作 $1$，答案即为所有数位的代价之和，记为 $s$。

原题转化为：找到 $n$ 的一个子序列，在最后一步直接把这个数删掉，求最多能“节省”多少代价。

注意到可以 dp 求解。设 $dp_{i,j}$ 表示考虑从左到右数的第 $i$ 到最后一位，在这一段中选出一个长度为 $j$ 的子串，最多节省多少代价。

设 $n_i$ 是 $n$ 从左到右数的第 $i$ 位，那么，在转移时，对于这一位，要么不选这一位作为最高位，则 $dp_{i,j}=dp_{i+1,j}$；要么选这一位作为最高位，那么 $dp_{i,j}=dp_{i+1,j-1}+v_{n_i}-n_i\times10^{j-1}$。取 $\max$ 就可以了。

从后往前 dp，最后输出 $s-\max(0,\max\limits_{i=1}^{j_{\max}}dp_{1,i})$ 即可。

赛时为了保险把 dp 时选取的 $j$ 的最大值设成了 $9$，但实际上并不用考虑那么多位啦。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int c;
int v[15],dp[100005][15],a[100005];
int p10[15]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
void mian(){
	string n;cin>>n;int l=n.length();
	for(int i=0;i<l;i++)a[i+1]=n[i]-'0';
	for(int i=1;i<=9;i++)cin>>v[i];
	memset(dp,0,sizeof dp);
	int s=0;
	for(int i=1;i<=l;i++)s+=v[a[i]];
	for(int i=l;i>=1;i--){
		for(int j=1;j<=min(9ll,l-i+1);j++){
			dp[i][j]=max(dp[i+1][j],dp[i+1][j-1]+v[a[i]]-p10[j-1]*a[i]);
		}
	}
	int ans=0;
	for(int i=1;i<=9;i++)ans=max(ans,dp[1][i]);
	cout<<s-ans<<endl;
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>c;
	int t;cin>>t;
	while(t--)mian();
	return 0;
}