求助,#29不过
查看原帖
求助,#29不过
735136
lubochen10楼主2022/10/10 12:56
#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;
}
2022/10/10 12:56
加载中...