yukicoder No.288 貯金箱の仕事

問題

No.288 貯金箱の仕事 - yukicoder

解法

まず, ゆきうさぎさんはまずお金を全部貯金箱さんに預けて, そのあと貯金箱さんがなるべく少ない硬貨の枚数でゆきうさぎさんに返せば良い, ということがわかります。つまり, この問題は本質的には「お金をなるべく少ない硬貨で作ろう！」といういつもの DP です。

ただ, 今回は作るべきお金が非常に高額なので単純に dp[n][money] = (n 番目まで使って money 円を作る最小の硬貨数) とすることは出来ません。ただ, 実は money が A[N-1] * A[N-1] 円以上であれば, 必ず A[N-1] を使うのが得, ということが言えるので, dp するときの money は A[N-1] * A[N-1] 円まで調べておけば答えを求められます。

なんで money が B = A[N-1] * A[N-1] 円以上であれば, 必ず A[N-1] を使うのが得なのかを考えます。
money が B 円以上の時で, A[N-1] 円使わないほうが良いような組み合わせがあるとしましょう。すると, A[N-2] 円以下の硬貨は必ず A[N-1] 枚以上使わないといけません。そうしないと B 円以上のお金を作れないので。
この時, 使う硬貨をそれぞれ とすると, 鳩の巣原理により, ある組み合わせ (i, j) について, と で A[N-1] で割った余りが等しいものが存在します。この i, j を使って の A[N-1] で割った余りを計算すると, これは 0 になります。この和の分は A[N-1] を使って支払ってお金を錬成するほうが絶対に得なので, money が B 円以上の時は A[N-1] 円を使うほうが得です。

const int MAXN = 501;
const ll INF = 1ll<<55;
int A[MAXN];
ll K[MAXN];
int N;
ll M;

ll dp[MAXN*MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> M;
    ll sum = 0;
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < N; i++) {
        cin >> K[i];
        sum += A[i]*K[i];
    }
    if (sum < M) {
        cout << -1 << endl;
        return 0;
    }
    for (int j = 0; j <= A[N-1]*A[N-1]; j++) dp[j] = INF;
    dp[0] = 0;
    for (int i = 0; i < N; i++) for (int j = 0; j <= A[N-1]*A[N-1]; j++) {
        if (A[i] <= j) dp[j] = min(dp[j], dp[j-A[i]] + 1);
    }
    ll ans = 0;
    ll T = sum-M;
    if (T > A[N-1]*A[N-1]) {
        ll cnt = T-A[N-1]*A[N-1];
        ans += cnt/A[N-1]+1;
        T -= ans*A[N-1];
    }
    ans += dp[T];
    if (ans >= INF) ans = -1;
    cout << ans << endl;
    return 0;
}