题解 | #牛牛去买球#

#include<cstring>
using namespace std;
int inf=0x3f3f3f3f;
long dp[20200];
int a[55],b[55],c[55];
int main()
{
	int n,k,v=2e4-2;
	long ans;
	ans=inf;
	cin>>n>>k;
	for(int i=1;i<=n;i++)	cin>>a[i];
	for(int i=1;i<=n;i++)	cin>>b[i];
	for(int i=1;i<=n;i++)	cin>>c[i];	
	memset(dp,0x3f,sizeof(dp));
	dp[0]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=v;j>=(a[i]-1);j--)
		{
			dp[j]=min(dp[j],dp[j-(a[i]-1)]+c[i]);
		}
	}
	for(int i=k;i<=v;i++)
		ans=min(ans,dp[i]);
	memset(dp,0x3f,sizeof(dp));
	dp[0]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=v;j>=(b[i]-1);j--)
		{
			dp[j]=min(dp[j],dp[j-(b[i]-1)]+c[i]);
		}
	}
	for(int i=k;i<=v;i++)
		ans=min(ans,dp[i]);
	memset(dp,0x3f,sizeof(dp));
	dp[0]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=v;j>=(a[i]+b[i]);j--)
		{
			dp[j]=min(dp[j],dp[j-(a[i]+b[i])]+c[i]);
		}
	}
	for(int i=2*k-1;i<=v;i++)
		ans=min(ans,dp[i]);	
	if(ans==inf) cout<<-1<<endl;
	else cout<<ans;
}