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

xu_zhihao · 2024-10-14 22:53:11 · 题解

题目描述

• 我这道题是用 DP 做的，我觉得是 DP 好题。

• 观察题目，不难发现若使用第二种操作， n 当时的长度定 \le 6。所以即可设 DP 状态为 dp_{i,j,k} 表示从后往前第 i 位是使用了哪一种操作被消除的，从后往前 i 个位置总共有 k 个数字是被操作 2 消除的。dp 转移显而易见，暴力转移 dp_{i,1,k}=\min(dp_{i+1,1,k},dp_{i+1,2,k})+v_{n_i},dp_{i,2,k}=\min(dp_{i+1,1,k-1},dp_{i+1,2,k-1})+n_i\times 10^{k-1}。 n_i 表示 n 从左往右第 i 位所表示的数。而从右往左推 DP 是为了更好的转移第二个操作。

• 最后时间复杂度为 O(|n|T)，有常数。空间复杂度 O(|n|)，有常数。|n| 表示 n 的位数。

代码

#include<bits/stdc++.h>
using namespace std;
long long dp[100010][2][7];
long long INF=1e18;
long long a[10];
char s[100010];
int n;
void Init(){
    for(int j=0;j<=1;j++){
        for(int k=0;k<=6;k++){
            dp[n+1][j][k]=0;
        }
    } 
    for(int i=1;i<=n;i++){
        for(int j=0;j<=1;j++){
            for(int k=0;k<=6;k++){
                dp[i][j][k]=INF;
            }
        } 
    }
    return;
}
long long Pow(long long a,long long b){
    long long ans=1;
    while(b){
        if(b&1){
            ans*=a;
        }
        a*=a;
        b>>=1;
    }
    return ans;
}
int main(){
    int c;
    scanf("%d",&c);
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%s",s+1);
        n=strlen(s+1);
        Init();
        for(int i=1;i<=9;i++){
            scanf("%lld",&a[i]);
        }
        for(int i=n;i>=1;i--){
            int mx=6;
            dp[i][0][0]=dp[i+1][0][0]+a[s[i]-'0'];
            for(int k=1;k<=mx;k++){ 
                dp[i][0][k]=min(dp[i+1][0][k],dp[i+1][1][k])+a[s[i]-'0'];
            }                       
            dp[i][1][1]=dp[i+1][0][0]+1ll*(s[i]-'0')*Pow(10,0);
            for(int k=2;k<=mx;k++){ 
                dp[i][1][k]=min(dp[i+1][0][k-1],dp[i+1][1][k-1])+1ll*(s[i]-'0')*Pow(10,k-1);
            }                       
        }
        long long ans=INF;
        for(int j=0;j<=1;j++){
            for(int k=0;k<=6;k++){
                if(j==1&&!k)continue;
                ans=min(ans,dp[1][j][k]);
            }
        }
        printf("%lld\n",ans);
    }
    return 0; 
}

UPD： 初始化 DP 一定要对，警钟长鸣。