求助,#29不过

CF19B Checkout Assistant

lubochen10 @ 2022-10-10 12:56:12

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
inline int read()
{
    int x=0,f=0;char ch=getchar();
    while(!isdigit(ch))f|=ch=='-',ch=getchar();
    while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
    return f?-x:x;
}
int w[2001];
long long c[2001],dp[4001],ans=2e12; 
int main()
{
    int n,vis;
    n=read();
    for(int i=1;i<=n;i++)
    {
        w[i]=read()+1,c[i]=read();
        vis=max(vis,w[i]);
    }
    vis+=n;
    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=n;i++)
     for(int j=vis;j>=w[i];j--)dp[j]=min(dp[j],dp[j-w[i]]+c[i]); 
    for(int i=n;i<=vis;i++)ans=min(ans,dp[i]); 
    cout<<ans;
    return 0;
}

by zhanglewei4598 @ 2023-04-12 13:28:23

@lubochen10 我刚开始也是,把 vis-1 就过了。。。


|