题意：
求确定n种货币面额x1..xn满足 x1=1 且xi为xj的整数倍（i>j）
给定n个物品价格ai 求使用上面货币最少需要硬币数（不能找零）
题解：
动态规划
听说网上的题解都是搜索的做法- - 只有一个人有说能用dp 但是没说怎么做
我想了一晚上 终于想出了dp的做法orz
f[i]表示最大货币面额为i 时 所需最少硬币数
转移方程：
f[i]=f[j]-Σ(a[k]/i)*(i/j-1) （j为i的因数，/为整除）
其实这个方程也不难
意思就是求每个物品能用几次i 硬币支付 而没有i 硬币要得到i 的价值就最少需要i/j个硬币
所以每用一次i 硬币就能减少使用 i/j-1个硬币
优化：
这样做对每个i 可能有√a 个因数 所以时间复杂度为O(n√(maxa)maxa)
显然会超时 能做一个优化 j只要取(i/i的质因数)
否则设 i/j 不是质数 i/j存在>1的因数d 则加入i/d这个面值以后 只会使答案更优
这样i的质因数个数为log(i) 所以时间复杂度为O(nlog(maxa)maxa)
【bzoj3233】【ahoi2013】找硬币,布布扣,bubuko.com
原文：http://www.cnblogs.com/g-word/p/3627003.html