P11188 「KDOI-10」商店砍价

· · 题解

难绷 dp。

思路

通过观察数据范围，发现 v_i\le 10^5 的数据范围十分有限，所以贪心地采用第二种删除策略一起删除的数的个数一定不超过 5 个，因为剩下的 n 必然有 n\le 10^5 而 n 的每位均不为 0 所以最多剩 5 个。

有了上述结论依然没法贪心，考虑从 dp 下手设 dp_{i,j} 表示前 i 个数有 j 个数采用第二种删除策略的最小代价。因为对于第一种删除策略只关心被是否被删掉而不关心顺序所以将整个大数反转以便 dp，得到转移式：

dp_{i,j}=\min(dp_{i-1,j-1}+10^{j-1}\times a_i,dp_{i-1,j}+v_{a_i}),i\in[1,n],j\in[0,5]

答案就是 \min\{dp_{n,i}\}。

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5,xN=1e7+5,mN=1e4+5,mod=1e9+7;
namespace FreedomKing_qwq{};
using namespace FreedomKing_qwq;
namespace FreedomKing_qwq{
#define lc (p<<1)
#define rc (p<<1|1)
    inline int qread(){
#define qr qread()
        int x=0,c=getchar(),t=1;
        while(c<'0'||c>'9'){
            t^=(c=='-');
            c=getchar();
        }
        while(c>='0'&&c<='9'){
            x=(x<<3)+(x<<1)+c-'0';
            c=getchar();
        }
        return (t?x:-x);
    }
    inline void qwrite(int x){
#define qw(_) qwrite(_)
#define qws(_) qw(_),putchar(' ')
#define qwe(_) qw(_),putchar('\n')
        if(x<0) x=-x,putchar('-');
        if(x>9) qwrite(x/10);
        putchar(x%10+'0');
        return;
    }
    inline int qpow(int x,int p,int mod){
        x=(p?x:1);
        mod=(mod?mod:LONG_LONG_MAX);
        int t=1;
        while(p>1){
            if(p&1) t=(t*x)%mod;
            x=(x*x)%mod;
            p>>=1;
        }
        return (x*t)%mod;
    }
    inline int gcd(int x,int y){return (x%y==0?y:gcd(y,x%y));}
    inline int lcm(int x,int y){x/=gcd(x,y);return (x*y);}
    inline int max(int x,int y){return (x>y?x:y);}
    inline int min(int x,int y){return (x<y?x:y);}
    inline int abs(int x){return (x>0?x:-x);}
}
int dp[N][6],v[10];
string s;
signed main(){
    qr;
    int T=qr;
    while(T--){
        cin>>s;
        for(int i=1;i<=9;i++) v[i]=qr;
        int len=s.size();
        reverse(s.begin(),s.end());
        s=" "+s;
        memset(dp,0,sizeof(dp));
        for(int i=0;i<=5;i++) dp[len][i]=LONG_LONG_MAX;
        for(int i=1;i<=len;i++){
            dp[i][0]=dp[i-1][0]+v[s[i]-'0'];
            for(int j=1,t=1;j<=5;j++,t*=10) dp[i][j]=min(dp[i-1][j-1]+t*(s[i]-'0'),dp[i-1][j]+v[s[i]-'0']);
        }
        int ans=LONG_LONG_MAX;
        for(int i=0;i<=5;i++) ans=min(ans,dp[len][i]);
        qwe(ans);
    }
    return 0;
}