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