首页 > 代码库 > [bzoj1531][POI2005]Bank notes

[bzoj1531][POI2005]Bank notes

2024-08-21 15:45:54   221人阅读

Description

技术分享拥有一套先进的货币系统,这个系统一共有技术分享种面值的硬币,面值分别为技术分享.但是每种硬币有数量限制,现在我们想要凑出面值技术分享求最少要用多少个硬币.

Input

第一行一个数技术分享.

第二行技术分享个整数技术分享.

第三行技术分享个整数技术分享,表示每种硬币的个数.

最后一行一个数技术分享,表示要凑的面值数量.

Output

一行一个数,表示最少需要付的硬币数.

Sample Input

3
2 3 5
2 2 1
10

Sample Output

3

HINT

技术分享

技术分享

Solution

技术分享表示用前技术分享种硬币凑出价值技术分享所需最少硬币数.

技术分享

对于对技术分享取模结果相同的技术分享,可以用单调队列进行优化.

#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 205
#define M 20005
using namespace std;
int f[N][M],b[N],c[N],q[M],h,t,n,m;
inline void init(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&b[i]);
    for(int i=1;i<=n;++i)
        scanf("%d",&c[i]);
    scanf("%d",&m);
    for(int i=0;i<=n;++i)
        for(int j=1;j<=m;++j)
            f[i][j]=M;
    for(int i=1;i<=n;++i){
        for(int k=0;k<b[i];++k){
            h=1;t=0;
            for(int j=k;j<=m;j+=b[i]){
                while(h<=t&&(j-q[h])/b[i]>c[i]) ++h;
                q[++t]=j;
                while(h<t&&f[i-1][q[t]]<=f[i-1][q[t-1]]+(j-q[t-1])/b[i]){
                    q[t-1]=q[t];--t;
                }
                f[i][j]=min(f[i-1][q[h]]+(j-q[h])/b[i],M);
            }
        }
    }
    printf("%d\n",f[n][m]);
}
int main(){
    freopen("bag.in","r",stdin);
    freopen("bag.out","w",stdout);
    init();
    fclose(stdin);
    fclose(stdout);
    return 0;
}

[bzoj1531][POI2005]Bank notes


联系
我们