01背包0分求助
查看原帖
01背包0分求助
661595
a2lyaXNhbWUgbWFyaXNh楼主2022/8/24 14:12

RT

根据题解里面的作法写的

加了初始化也没用QAQ(虽然没有爬过来,但我登上自己的CF号看的)

求调:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int w[2050],c[2050],dp[114514];
int ans=2e12;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>c[i];
		w[i]++;
		m=max(m,w[i]);
	}
	m+=n;
	for(int i=1;i<=n;i++)
		for(int j=m;j>=w[i];j--)
			dp[j]=min(dp[j],dp[j-w[i]]+c[i]);
	for(int i=1;i<=m;i++)
		ans=min(ans,dp[i]);
	cout<<ans;
	return 0;
}
2022/8/24 14:12
加载中...