TopCoder SRM420 Div1Hard
問題
何種類かの硬貨がたくさんあり、それぞれ額面が決まっている。常に1単位硬貨が存在する。
ある両替機は、いくらかのお金(2単位以上)を受け付けて、次の規則で両替する。
「2枚以上の硬貨に両替する。但し、枚数は可能な限り少なくする。枚数が同じときは、降順に硬貨の額面を並べた時、辞書順最大のものにする。」
この両替機を使って、ある金額をすべて1単位硬貨にしたい。最初にある金額を投入し、そのあとは出てきた硬貨を投入する。何回投入しないといけないか。
解法
金額がとても大きいのが問題だが、硬貨はどれも1000単位以下である。
ここで、100万単位以上については「100万以下になるまで、最大の硬貨を出す」戦略が使えることがわかる。
すると、金額の上限を100万とみなすことができ、100万は小さいのでDPやるだけである。
コード
#include <vector> using namespace std; class ChangeOMatic { vector<int> coins; int dpA[1002001], dpB[1002001], fromA[1002001], fromB[1002001]; int cost[50]; public: long long calc(int V) { if(V==0) return 0; long long ret = 1; ret += cost[fromB[V]]; V -= coins[fromB[V]]; while(true){ if(fromA[V]<0) break; ret += cost[fromA[V]]; V -= coins[fromA[V]]; } return ret; } long long howManyRounds(vector<int> out, long long in) { coins = out; dpA[0] = 0; dpB[0] = 0; fromA[0] = -1; fromB[0] = -1; dpA[1] = 1; dpB[1] = 1; fromA[1] = -1; fromB[1] = -1; for(int i=2;i<=1002000;i++){ dpA[i] = 1002002; dpB[i] = 1002002; fromA[i] = -1; fromB[i] = -1; for(int j=coins.size()-1;j>=0;j--){ if(i >= coins[j]){ if(dpA[i] > 1+dpA[i-coins[j]]){ dpA[i] = 1+dpA[i-coins[j]]; fromA[i] = j; } } if(i > coins[j]){ if(dpB[i] > 1+dpA[i-coins[j]]){ dpB[i] = 1+dpA[i-coins[j]]; fromB[i] = j; } } } } cost[0] = 0; for(int i=1;i<coins.size();i++){ cost[i] = 1; int t = coins[i]; cost[i] += cost[fromB[t]]; t -= coins[fromB[t]]; while(true){ if(fromA[t]<0) break; cost[i] += cost[fromA[t]]; t -= coins[fromA[t]]; } } long long mn = max((in - 1000000)/coins[coins.size()-1], 0LL); return calc((int)(in-mn*coins[coins.size()-1])) + mn*cost[coins.size()-1]; } };