SRM458 Div1 Medium

450
かなり悩んだ。
例えば、硬貨が価値1のものと価値Aのものしかない場合、価値Aで払いきれない分(あまり)は価値1の硬貨で払うしかない。
同様に、価値Aの次に大きい硬貨が価値A*Bだった場合、価値A*Bで払いきれない分(あまり)は価値Aを使ってできる限り払うことになる。

const int N = 50;
const int M = 100000+1;

int t[M];

int rec(int mx, vector<int> v)
{
  if( t[mx] != -1 )return t[mx];

  int mn = 0;

  for(int i=0; i<v.size(); ++i){
    mn += v[i] / mx;
  }

  for(int i=2; mx*i <= v.back(); ++i){
    int sum = 0;
    for(int j=0; j<v.size(); ++j){
      sum += v[j] % (mx * i) / mx;
    }
    mn = min( mn, rec(mx * i, v) + sum );
  }

  return t[mx] = mn;
}

class NewCoins {
public:
  int minCoins(vector <int> v) {

    fill( t, t + M, -1 );
    sort( ALL(v) );

    return rec(1, v);
  }
};