[パナソニックプログラミングコンテスト2021(ABC231)] E - Minimal payments
[Q] https://atcoder.jp/contests/abc231/tasks/abc231_e
本番で解けなかったようだ。あっさりリベンジ。
1. メモ化再帰で、memo[N] = N円払うのに必要な枚数で管理
2. 状態の遷移は3パターン
(a) お札でおつりをもらう
(b) 小銭でぴったりはらう
(c) 小銭でおつりをもらう
N=3 X=87
A: 1 10 100
0. 87円を払うのに適した硬貨は、lower_boundで前後を見つける。
over: 100円
low: 10円
(a) お札でおつり
100円払って、13円のおつりをもらう。
dfs(87) = dfs(100) + dfs(13)
~~~~~~~~ 1枚
(b) 小銭でぴったり
80円払って、7円払う。
dfs(87) = dfs(80) + dfs(7)
~~~~~~~ 8枚
(c) 小銭でおつり
dfs(87) = dfs(90) + dfs(3)
~~~~~~~ 9枚
dfs(N) = dfs(a) + dfs(b)
に分解できるが、dfs(a)は値が判明しているはずなので、直入れすればいい。
memoには次のデータが格納されるはず。
memo[0]:0
memo[3]:3
memo[7]:7
memo[13]:4
memo[87]:5
memo[87]:5 が答え実装
ll N, X;
vector<ll> A;
map<ll, ll> memo;
ll dfs(ll N) { // 87
if (memo.count(N)) return memo[N];
memo[N] = oo;
ll ret = oo;
// 100
auto it = lower_bound(all(A), N);
if (it != A.end()) {
ret = 1 + dfs(*it - N); // 100-13
}
// 10
if (it != A.begin()) {
--it;
ll x = N / (*it);
ll mx = N % (*it);
chmin(ret, x + dfs(mx)); // 10*8 + 7
if (mx > 0) {
chmin(ret, x + 1 + dfs((*it) - mx)); // 10*9 - 3
}
}
return memo[N] = ret;
}
int main() {
cincout();
cin >> N >> X;
A.reserve(N);
rep(i, N) {
ll a;
cin >> a;
A.push_back(a);
}
memo[0] = 0;
dfs(X);
cout << memo[X] << endl;
}