题解：P11188 「KDOI-10」商店砍价

cff_0102 · 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;
}