NewCoins
日課消化。Div1の450。DPで解いたけど、メモ化再帰の方が計算時間は短いかも。
このコードだけ見ても、やってること分かりにくいかもです。
各整数の余りの処理をDPで最適化するアルゴリズムになっています。
#include <algorithm> #include <iostream> #include <map> #include <numeric> #include <set> #include <sstream> #include <string> #include <vector> #include <math.h> using namespace std; #define FOR(i,s,e) for (int i = int(s); i != int(e); i++) #define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++) #define ISEQ(c) (c).begin(), (c).end() class NewCoins { public: int minCoins(vector<int> price) { int n = (int)price.size(); sort(price.begin(),price.end()); int m = price[n-1]; vector<int> num(m+1,0); int result = 0; for (int i=1; i<=m; i++){ int rest = 0; for (int j=0; j<n; j++ ){ num[i] += price[j]%i; rest += price[j]/i; } for ( int j=2; j<=sqrt(i); j++ ){ if((i%j)==0){ int sum1 = 0; int sum2 = 0; for(int k=0; k<n; k++){ sum1 += (price[k]%i)/j; sum2 += (price[k]%i)/(i/j); } int sum = min(sum1 + num[j] , sum2 + num[i/j]); if(num[i] > sum) num[i] = sum; } } int test = num[i] + rest; if(result == 0 || result > test) result = test; } return result; } };