| Day10-例1 |
| 难度级别：B； 运行时间限制：1000ms； 运行空间限制：256000KB； 代码长度限制：2000000B |
|
试题描述
|
|
给定N个物品，价格分别为A1, A2…AN。设计一套面值互不相等的硬币，面值从小到大分别为c1, c2, c3…。其中c1=1，对于正整数i(i>1)，ci必须是ci-1的整数倍。
N个物品必须分开购买，并且购买时不允许找零。问购买全部N个物品所需要的硬币个数总和的最小值。 |
|
输入
|
|
第一行，一个整数N。
第二行，N个整数，A1、A2...AN。 |
|
输出
|
|
一行，一个整数，表示购买全部N个物品所需要的硬币个数总和的最小值。
|
|
输入示例
|
|
2
25 102 |
|
输出示例
|
|
4
|
|
其他说明
|
|
N<=50，Ai<=100000
|
题解：数据范围100000,上来先想到什么斜率优化啊什么矩阵啊什么奇奇怪怪的东东。。。。结果这道题用到了欧拉爷爷的一个定理：
[n/1]+[n/2]+...+[n/n]=O(nlogn)。。。。
于是窝萌可以枚举i的倍数或约数来转移。原来只用面值为j的买物品A[k]需要[A[k]/j]个，现在如果用面值为i的话可以减少[A[k]/j]*[j/i-1]个，然后更新答案即可。设f[i]表示最大面值为i时所需硬币的最小总个数。每次用减少完的tmp更新。最后取最小的f。
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<stack> 6 #include<queue> 7 #include<cstring> 8 #define PAU putchar(‘ ‘) 9 #define ENT putchar(‘\n‘) 10 #define REN(x) for(ted*e=fch[x];e;e=e->nxt) 11 using namespace std; 12 const int maxn=50+10,maxm=100000+10,maxv=100000,inf=-1u>>1; 13 int f[maxm],A[maxn],n; 14 inline int read(){ 15 int x=0,sig=1;char ch=getchar(); 16 for(;!isdigit(ch);ch=getchar())if(ch==‘-‘)sig=0; 17 for(;isdigit(ch);ch=getchar())x=10*x+ch-‘0‘; 18 return sig?x:-x; 19 } 20 inline void write(int x){ 21 if(x==0){putchar(‘0‘);return;}if(x<0)putchar(‘-‘),x=-x; 22 int len=0,buf[15];while(x)buf[len++]=x%10,x/=10; 23 for(int i=len-1;i>=0;i--)putchar(buf[i]+‘0‘);return; 24 } 25 int main(){ 26 for(int i=1;i<=100000;i++)f[i]=inf; 27 n=read(); 28 f[1]=0;for(int i=1;i<=n;i++)A[i]=read(),f[1]+=A[i]; 29 for(int i=1;i<=maxv;i++) 30 for(int j=i*2;j<=maxv;j+=i){ 31 int tmp=f[i];int c=j/i-1; 32 for(int k=1;k<=n;k++)tmp-=(A[k]/j)*c; 33 f[j]=min(f[j],tmp); 34 } 35 int ans=inf; 36 for(int i=1;i<=maxv;i++)ans=min(ans,f[i]);write(ans); 37 return 0; 38 }
原文：http://www.cnblogs.com/chxer/p/4729767.html