SRM 458 Div 1 - NewCoins

张文泰 posted @ 2010年1月16日 01:40 in Art of Science with tags TopCoder 动态规划 , 2219 阅读

完整的题目描述在这里

题目给了我们一些货物的价格a1,...,am(不超过100000),要我们构造一种货币面值的方案x1,...,xn,使得所需要的纸币数量尽可能少。货币面值的方案必须满足

  • x1=1。
  • 对于i<j,xi一定是xj的约数。

注意到不需要给出面值的方案,只是要求输出最少的张数,那么我们可以用动态规划解决。对于一个确定的方案,由于上述的性质,我们一定是用贪心的方法来付款。另外,价格不会超过100000,所以需要考虑的最大面值也是100000。对于一个面额xi,付完款之后得到的余额是a1%xi,...,am%xi。我们令f(i)表示用面值大于等于i的货币方案所付款所需要的纸币数量, 那么f(i)=min{f(j)+余额用i付款的张数 | i为j的约数}。具体的代码如下:

public class NewCoins {
  static final int MAXN = 100000;
  public int minCoins(int[] price) {
    int n = price.length;
    int[] f = new int[MAXN+1];
    for (int i = MAXN; i>0; i--) {
      for (int j = 0; j<n; j++)
        f[i] += price[j]/i;
      for (int j = 2*i; j<=MAXN; j += i) {
        int tmp = f[j];
        for (int k = 0; k<n; k++)
          tmp += (price[k]%j)/i;
        if (f[i]>tmp) f[i] = tmp;
      }
    }
    return f[1];
  }
}

至此,问题就解决了。


本作品遵循“署名-非商业性使用-相同方式共享 3.0 Unported”协议,转载请注明来自richard-desktop
Creative Commons License

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter