问题 A: 找硬币
时间限制: 1 Sec 内存限制: 64 MB
提交: 144 解决: 43
[提交][状态]
题目描述
小蛇是金融部部长。最近她决定制造一系列新的货币。假设她要制造的货币的面值为x1,x2,x3… 那么x1必须为1，xb必须为xa的正整数倍（b>a）。例如 1，5，125，250就是一组合法的硬币序列，而1，5，100，125就不是。不知从哪一天开始，可爱的蛇爱上了一种萌物——兔纸！从此，小蛇便走上了遇上兔纸娃娃就买的不归路。某天，小蛇看到了N只可爱的兔纸，假设这N 只兔纸的价钱分别是a1,a2…aN。现在小蛇想知道，在哪一组合法的硬币序列下，买这N只兔纸所需要的硬币数最少。买兔纸时不能找零。
输入
第一行，一个整数N，表示兔纸的个数
第二行，N个用空格隔开的整数，分别为N只兔纸的价钱
输出
一行，一个整数，表示最少付的钱币数。
样例输入
2
25 102
样例输出
4
提示
样例解释：共有两只兔纸，价钱分别为25和102。现在小蛇构造1，25，100这样一组硬币序列，那么付第一只兔纸只需要一个面值为25的硬币，第二只兔纸需要一个面值为100的硬币和两个面值为1的硬币，总共两只兔纸需要付4个硬币。这也是所有方案中最少所需要付的硬币数。
1<=N<=50, 1<=ai<=100,000
正解是DP,但可以用DFS.
新的硬币一定是原来的整数倍，并且是质数。
现在我们假设最开始要全用1付，则sum[i]=w[i]。而我们每去枚举一个新的倍数x，那这个倍数x只能更改原来最大值硬币的支付个数（它可以合并原来最大值的每x个，剩下的还要由原来的最大值付）。那么a[i]就用来表示上一个最大值所要支付的对应面值的硬币数，那么在下一层深搜时，就可以确定他要支付多少个了。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int read()
{
int sum=0,f=1;char x=getchar();
while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
while(x>='0'&&x<='9'){sum=(sum<<1)+(sum<<3)+x-'0';x=getchar();}
return sum*f;
}
int n,m,a[55],b[55],ans,pri[100005],tot,mark[100006];
void init()
{
for(int i=2;i<=100000;i++)
{
if(!mark[i])pri[++tot]=i;
for(int j=1;j<=tot;j++)
{
if(pri[j]*i>a[n])break;
mark[pri[j]*i]=1;
if(i%pri[j]==0)break;
}
}
}
inline void dfs(int y,int x,int sum)
{
int s=0,c[55],js=0;
for(int i=1;i<=n;i++)
s+=a[i]%pri[y],a[i]/=pri[y];
sum+=s;
if(sum>=ans)return;
memcpy(c,a,sizeof(a));
if(a[n]!=1&&a[n]!=0)
{
for(int i=1;i<=tot;i++)
{
int h=pri[i]*x;if(h>m)break;
dfs(i,h,sum);
memcpy(a,c,sizeof(a));
}
}
else
{
for(int i=1;i<=n;i++)if(a[i])js++;
ans=min(ans,sum+js);
}
}
int main()
{
n=read();
for(int i=1;i<=n;i++)a[i]=read(),ans+=a[i];
sort(a+1,a+n+1);m=a[n];memcpy(b,a,sizeof(a));
init();
for(int i=1;i<=tot&&pri[i]<=m;i++)
dfs(i,pri[i],0),memcpy(a,b,sizeof(b));
cout<<ans;
}