自动搬运

查看原文

来自洛谷，原作者为

	谋事在人 莫愁前路无知己，天下谁人不OI

搬运于2025-08-24 22:08:27，当前版本为作者最后更新于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;
}

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