时间限制: 1 Sec 内存限制: 64 MB
题目描述
小蛇是金融部部长。最近她决定制造一系列新的货币。假设她要制造的货币的面值为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
题解
虽然说是T1但是本着不会做就跳过的原则我还是果断把它忽略了……事实证明T3极其水，后来回来给这道题打了个dfs还有28分。刚开始以为是每一层的倍数都必须相同，然后自己在那里枚举得还挺high，后来发现不是那么回事，迷之尴尬。因为一贯是读完三道题，各自稍微想一下再开始按自己思路的有无集中做每一道题，所以有很多时候做完别的题再回来就对题意的理解出了偏差，下一次应该只要开始做就再读一遍题。
有一个结论是每一层的倍数都应该枚举素数。因为发行硬币的种类是不限的，所以每一个合数都可以由很多素数的乘积得到。想象一下枚举第一个素数p1,那么a[i]%p1是一定要用一元硬币去买的。下一层再枚举一个素数p2,(a[i]-a[i]%p1)%(p1*p2)一定是要用p1去买的，这样每一层枚举之后把a[i]/=p,下一层就仍可以按这样的方式枚举，相当于秦九韶算法的逆运算，ans即为余数之和，深搜时可以比较当前的summod和ans来及时停止无意义的枚举。有一个我刚开始没注意到的优化是如果p已经大于当前最大的a[i],再枚举p是没有用的，直接把summod+=sigma(a[i])然后更新答案就可以停止当前dfs了。
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int sj=100005; int n,a[55],tp,z,jd,p[sj],ge; long long ans; bool nprime[sj]; void dfs(int x,int st) { if(x>=ans) return; int b[55]; memcpy(b,a,sizeof(b)); for(int i=1;i<=ge;i++) { tp=x; if(a[n]<p[i]) { for(int j=st;j<=n;j++) tp+=a[j]; if(tp<ans) ans=tp; break; } for(int j=st;j<=n;j++) { z=a[j]/p[i]; tp+=a[j]-z*p[i]; a[j]=z; if(tp>=ans) break; } if(tp<ans) for(int j=st;j<=n;j++) { if(a[j]!=0) { dfs(tp,j); break; } if(j==n) ans=tp; } memcpy(a,b,sizeof(a)); } } void solve(int x) { nprime[0]=nprime[1]=1; for(int i=2;i<=x;i++) { if(!nprime[i]) p[++ge]=i; for(int j=1;j<=ge&&i*p[j]<=x;j++) { nprime[i*p[j]]=1; if(!(i%p[j])) break; } } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); if(jd<a[i]) jd=a[i]; ans+=a[i]; } solve(jd); sort(a+1,a+n+1,less<int>()); dfs(0,1); printf("%lld",ans); return 0; }