Banknotes

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1449 字
n种硬币，面值b_i、数量c_i，求凑出面额
一本通
例
正文

/*
原题：T1601 「一本通 5.5 例 5」Banknotes
题意：n 种硬币，面值 b_i、数量 c_i，求凑出面额 k 所需的最少硬币数。
思路：多重背包单调队列优化。对每种硬币按余数 r 分组，组内下标按 v 步进；
     状态 dp[j]=min(dp[j-t·v]+t)，化为在窗口长 lim+1 内取 min(dp_old[m']-m')+m，
     用单调队列维护 (dp_old[m']-m')。关键：候选必须用本物品处理前的 old 快照。
复杂度：时间 O(n·k)，空间 O(k)。
易错点：组内须用处理前的 old 数组做候选，否则原地复用会变成完全背包（无视数量上限）；
     初始化 dp[0]=0，其余 INF；窗口下界 m-lim 越界不入队。
*/
#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 i=0;i<n;i++){
        cin>>b[i];
    }
    for(int i=0;i<n;i++){
        cin>>c[i];
    }
    int k;
    cin>>k;
    const int INF=1e9;
    vector<int> dp(k+1,INF);
    dp[0]=0;
    for(int i=0;i<n;i++){
        int v=b[i],lim=c[i];
        vector<int> old=dp;
        for(int r=0;r<v;r++){
            deque<int> q;
            for(int j=r;j<=k;j+=v){
                int m=(j-r)/v;
                while(!q.empty()&&q.front()<m-lim){
                    q.pop_front();
                }
                if(!q.empty()){
                    int cand=old[q.front()*v+r]+(m-q.front());
                    if(cand<dp[j]){
                        dp[j]=cand;
                    }
                }
                while(!q.empty()&&old[q.back()*v+r]-q.back()>=old[j]-m){
                    q.pop_back();
                }
                q.push_back(m);
            }
        }
    }
    cout<<dp[k]<<'\n';
    return 0;
}
Banknotes

正文

一本通·提高篇的其它内容
