思路与算法

令old[s]为处理前几种纸币恰凑s的最少张数。处理面值b、数量c时，按s模b分组。写s=r+jb，转移为new[r+jb]=j+min(old[r+tb]-t)，其中j-c≤t≤j。滑动窗口用单调队列维护最小值。

正确性说明

枚举本种取j-t张，合法数量恰对应窗口区间。余下金额必须由前几种构成，因此窗口公式与完整数量枚举完全等价。单调队列仅删去窗口外或永远劣于后续元素的候选，不改变最小值，逐种归纳得最优张数。

复杂度

每种面值下每个金额入队出队至多一次，含数组初始化总O(nK)，空间O(K+n)。

易错点

窗口长度是c+1，不能遗漏0张方案。不可达状态不参与有穷转移；K=0答案0。数量可先截到K/b；最终不可达输出-1。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> b(n), c(n);
    for (int &x : b)
        cin >> x;
    for (int &x : c)
        cin >> x;
    int K;
    cin >> K;
    const int INF = 1000000000;
    vector<int> dp(K + 1, INF);
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        auto old = dp;
        fill(dp.begin(), dp.end(), INF);
        int cap = min(c[i], K / b[i]);
        for (int r = 0; r < b[i] && r <= K; r++) {
            deque<pair<int, int>> q;
            for (int j = 0, x = r; x <= K; j++, x += b[i]) {
                while (!q.empty() && q.front().first < j - cap)
                    q.pop_front();
                if (old[x] != INF) {
                    int v = old[x] - j;
                    while (!q.empty() && q.back().second >= v)
                        q.pop_back();
                    q.push_back({j, v});
                }
                if (!q.empty())
                    dp[x] = q.front().second + j;
            }
        }
    }
    cout << (dp[K] == INF ? -1 : dp[K]) << '\n';
}