题解 P5228 【[AHOI2013]找硬币】

· · 题解

更新于 2021.8.11

P5228 [AHOI2013]找硬币 题目传送门

个人感觉这题似乎并没有达到黑题应有难度，只是单纯的暴力dp而已qwq

woc，蓝了，我还说好不容易水了一篇假的黑题题解了，结果……

（我tmd没事反馈这道题干啥……

以下为题目解析

题目中规定任意两种货币之间都有倍数关系，要求用这些货币去买珂爱的兔纸，使用的货币数量最少，且没有找零

因为货币之间都有倍数关系，所以可以得出当存在几个小面额货币可以被一个大面额货币替代时，替代肯定是最优的

因此，可以得出状态转移方程 dp_{i \times j} = \min(dp_{i \times j},dp_i - chge) ，即买价格为 i \times j 的物品所需的货币数量等于原先的较优解与替换后的结果的较小值，其中 chge 表示将面值为 i 的货币替换成面值为 i \times j 的货币所节省下的货币数量

因为这题的数据范围为 n \leq 50 ,v \leq 100000 ，所以暴力dp是可以过的

下面是代码qwq

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int X=0,w=0;
    char ch=0;
    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
    while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
inline void write(int x) {
    static int stk[100], top = 0;
    if(x==0){putchar('0');return;}
    if(x<0){x=-x;putchar('-');}
    while(x){stk[++top]=x%10;x/=10;}
    while(top)putchar(stk[top--] ^ '0');
    return;
}
//祖传快读快输qwq
int n,maxn,ans=INT_MAX,a[55],dp[100010];
int main(){
    memset(dp,0x3f,sizeof(dp));
    dp[1]=0;
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        maxn=max(maxn,a[i]);
        dp[1]+=a[i];
    }
    ans=dp[1];
    for(int i=1;i<=maxn/2;i++){
        for(int j=2;j*i<=maxn;j++){
            int chge=0;
            for(int r=1;r<=n;r++)
                chge+=a[r]/(i*j);
            dp[i*j]=min(dp[i*j],dp[i]-(j-1)*chge);
            ans=min(ans,dp[i*j]);
        }
    }
    printf("%d\n",ans);
    return 0;
}

经实测，2.19s，1.15MB通过，求资瓷！