问题标题: 酷町堂：2424 最少的钱币 我10分

/*
f[j]=f[j],f[j-w[i]]+1
*/

#include<iostream>
using namespace std;

int fn[200001];//农夫 
int fd[200001];//店员 
int m=0;
int v[200];
int c[200]; 

void zop(int w)
{
    for(int i=m;i>=w;i--)
    {
        fn[i]=min(fn[i],fn[i-w]+1);
    }
}

void cp(int w)
{
    for(int i=w;i<=m;i++)
    {
        fn[i]=min(fn[i],fn[i-w]+1);
    }
}

void mp(int w,int c) 
{
    if(c*w>=m)
    {
        cp(w);
    }
    else
    {
        int k=1;
        while(k<c)
        {
            zop(k*w); 
            c-=k;
            k*=2;
        }
        zop(c*w);
    }
} 

int main()
{
    int n,t;
    cin>>n>>t;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>c[i];
        m+=c[i]*v[i];
    }
    if(m<t)
    {
        cout<<-1;
    }
    else
    {
        for(int i=1;i<=m;i++)
        {
            fn[i]=200001;
        }
        fn[0]=0;
        for(int i=1;i<=n;i++)
        {
            mp(v[i],c[i]);
        }
        
        for(int i=1;i<=m;i++)
        {
            fd[i]=200001;
        }
        fd[0]=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=v[i];j<=m;j++)
            {
                fd[j]=min(fd[j],fd[j-v[i]]+1);
            }
        }
        int minv=200020;
        for(int i=t;i<=m;i++)
        {
            minv=min(minv,fn[i]+fd[i-t]);
        }
        cout<<minv;
    }
    return 0;
}

@方亦欧 @王星河 @梁锦程 @陆麟瑞 @栾峻岩