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 我刚开始也是,把