SRM458 Div1 Medium(450) NewCoins
DP。値段rの製品を1とp以上の価値のコインc枚で払えるならば、dをpの約数として、価値dのコインを加えればc-r%p/d*d+d枚のコインで払える。pで払いきれなかった余りr%pのうちr%p/d*dをd枚のコインで払えるので。
実行時間がちょっと怖い。私のプログラムが悪いのか、問題のバランスがいいのか……。
#include <vector> #include <algorithm> #include <numeric> using namespace std; class NewCoins { public: int minCoins( vector <int> price ); }; int NewCoins::minCoins( vector <int> price ) { int n = (int)price.size(); int m = *max_element( price.begin(), price.end() ); vector<int> num( m + 1 ); for ( int i=m; i>=1; i-- ) { num[i] = 0; for ( int j=0; j<n; j++ ) num[i] += price[j]/i + price[j]%i; for ( int j=i*2; j<=m; j+=i ) { int t = num[j]; for ( int k=0; k<n; k++ ) t -= price[k]%j / i * (i-1); num[i] = min( num[i], t ); } } return num[1]; }