大佬求调
查看原帖
大佬求调
661913
liwenxi1145144444楼主2024/4/10 13:23
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,x,M,m,num[5005],p[5005][5005],h[5005][5005],dp[5005][5005];
signed main(){
	cin>>n>>x>>M>>m;
	for(int i=1;i<=n;i++){
		cin>>num[i];
		for(int j=1;j<=num[i];j++){
			cin>>p[i][j];
		}
		for(int j=1;j<=num[i];j++){
			cin>>h[i][j];
		}
	}
	for(int i=0;i<=n;i++){
		for(int j=0;j<=x;j++){
			dp[i][j]=5e9;
		}
	}
	dp[1][x]=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=x;j++){
			dp[i][j]=dp[i-1][max(0ll,j-m)];
			for(int k=1;k<=num[i];k++){
				dp[i][j]=min(dp[i][j],dp[i-1][max(0ll,j-min(M,m+h[i][k]))]+p[i][k]);
			}
		}
	}
	/*for(int i=1;i<=n;i++){
		for(int j=0;j<=x;j++){
			cout<<dp[i][j]<<" ";
		}
		cout<<"\n";
	}*/
	int minn=5e9;
	for(int i=1;i<=n;i++){
		if(dp[i][0]<5e9){
			minn=min(minn,dp[i][0]);
		}
	}
	if(minn==5e9){
		cout<<-1;
	}else{
		cout<<minn;
	}
	return 0;
}
2024/4/10 13:23
加载中...