KDOI-10」商店砍价 题解

Jluck · 2024-10-13 20:00:18 · 题解

本题比较水（雾

我们可以发现当 n 数位个数大于 5 时一定不优了，考虑最差情况 n 全是 1，v 全是 10^5 的情况可得，接下来就很好说了，我们只需要考虑剩下 n 的位数小于等于 5 的情况就可以了， 那么这部分解决了，接下来来解决正常选择部分，那么也很简单在数组 v 上查询即可。

转移方程详见代码部分。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+1;
int c,t,v[N],f[N][6];
char s[N];
signed main(){
    cin>>c>>t;
    while(t--){
        cin>>s+1;
        int n=strlen(s+1);
        for(int i=1;i<=9;++i)
            cin>>v[i];
        int ans=0,mins=0;
        memset(f,0x3f,sizeof f);
        for(int i=1;i<=n+1;++i)
            f[i][0]=0; 
        for(int i=n;i>=1;--i){
            ans+=v[s[i]-'0'];//处理普通情况
            for(int j=1;j<=5;++j)
                f[i][j]=min(f[i+1][j],f[i+1][j-1]+(int)pow(10,j-1)*(s[i]-'0')-v[s[i]-'0']);//当前是选择遗传下来还是当开头
        }
        for(int i=n;i>=1;--i)
            for(int j=1;j<=5;++j)
                mins=min(mins,f[i][j]);
        cout<<ans+mins<<endl;
    }
    return 0;
}