SRM458 Div1 Medium(450) NewCoins

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];
}