Jisoo

显然找硬币和付钱是两个过程

然而最多给多少钱呢

有应该找最多多多少呢？

方案一

时间绰绰有余，我们开的大一点

证明

找钱的数量不会超过$V_{max}^2$

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int T;
int n;
int v[105];
int f1[34405];
int f2[24405]; 
int c[105];
int maxx;
int ans;
int sum;
int main(){
    scanf("%d%d",&n,&T);
    for(int i=1;i<=n;++i){
        scanf("%d",&v[i]);
    }
    for(int i=1;i<=n;++i){
        scanf("%d",&c[i]);
    }
    memset(f2,0x3f,sizeof(f2));
    memset(f1,0x3f,sizeof(f1));
    maxx=f2[0];
    f2[0]=f1[0]=0;
    for(int i=1;i<=15000;++i){
        for(int j=1;j<=n;++j){
            if(i>=v[j]){
                f2[i]=min(f2[i],f2[i-v[j]]+1);
            }
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=c[i];j<<=1){
            for(int z=T+15000;z>=j*v[i];--z){
                f1[z]=min(f1[z],f1[z-j*v[i]]+j);
            }
            c[i]-=j;
        }
        if(c[i]){
            for(int z=T+15000;z>=c[i]*v[i];--z){
                f1[z]=min(f1[z],f1[z-c[i]*v[i]]+c[i]);
            }
        }
    }
    ans=maxx;
    for(int i=0;i<=15000;++i){
        ans=min(ans,f1[i+T]+f2[i]);
    }
    if(ans==maxx)
    cout<<-1;
    else
    cout<<ans;
    return 0;
}