| 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个物品所需要的硬币个数总和的最小值。 |
| 输入示例 |
| 225 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 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 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 }