lg5228

谋事在人 · 2019-10-28 22:07:24 · 题解

1. 题目解释

定义任意多种货币满足任意两种货币之间都有倍数关系，用这些货币去购买n种物品，要求购买时使用的货币总数（注意是数量）最少。（必须正好凑齐）

2.题目分析

考虑到每个货币都是比它小的货币面值的倍数，所以每几个小面值的货币都可以被一个大面值（已定义的）的货币代替，而且不会有损失，可以采用贪心的思想。

题目中有多种可能的定义货币方式，例如若20元为最大面值可以定义为{1,4,20}或{1,5,20}，20元为最大面值时的解答依赖于4元或5元的情况，且可以取min，看数据范围，n=50,v=100000，O(nv√v)的暴力dp(常数小）可以过。

3.dp思路

可以定义dp[i]为以i为最大面值时的最少使用货币个数。

枚举ij<=maxn的j，dp[ij]=min(dp[ij],dp[i]-minus）;（ij代表i*j）

此处的minus为所有兔子中可以把j个面值为i的货币换成面值为i*j的货币时可以减少的货币数量。

4.贴代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,maxn,ans = 1e9+7,a[100],dp[100010];

int main(){
    memset(dp,0x3f,sizeof(dp));
    dp[1]=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        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++){//枚举i与j
            int minus=0;
            for(int r=1;r<=n;r++)//暴力求替换后的收益
                minus+=a[r]/(i*j);
            dp[i*j]=min(dp[i*j],dp[i]-(j-1)*minus);//dp
            ans=max(ans,dp[i*j]);//防作弊
        }
    }
    printf("%d\n",ans);
    return 0;
}

最后吐槽一句，这个题真的是黑题难度吗...