蒟蒻求助 WA#7
  • 板块CF730J Bottles
  • 楼主huangziqinFJ人炖蒟蒻
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/9/26 17:50
  • 上次更新2023/10/27 09:53:19
查看原帖
蒟蒻求助 WA#7
185223
huangziqinFJ人炖蒟蒻楼主2022/9/26 17:50
#include<bits/stdc++.h>
using namespace std;

const int N=101;

int n,wat=0,watt=0,m,f[N][N];

struct dataa
{
	int wa;
	int bo;
}a[N];

bool cmp(dataa x,dataa y)
{
	return x.bo>y.bo;
}

int main()
{
	scanf("%d",&n);
	wat=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i].wa);
		wat+=a[i].wa;
	}
	for(int i=1;i<=n;i++) scanf("%d",&a[i].bo);
	sort(a+1,a+1+n,cmp);
	watt=wat;
	for(int i=1;i<=n;i++)
	{
	//	cout<<watt<<" "<<a[i].bo<<endl;
		if(watt-a[i].bo<=0)
		{
			printf("%d ",i);
			m=i;
			break;
		}
		else
		{
			watt-=a[i].bo;
		}
	}
	memset(f,0x3f3f3f,sizeof(f));
	f[0][0]=0;
	for(int i=1;i<=n;i++)//枚举n个瓶子
	{
		for(int o=min(i,m);o>=1;o--)//枚举用了o个瓶子
		{
			for(int j=a[i].wa;j<=wat;j++)//枚举装了多少水
			{
				for(int k=0;k<=a[i].bo-a[i].wa;k++)//枚举这个瓶子被移入了多少水
				{
					f[o][j]=min(f[o][j],f[o-1][j-a[i].wa-k]+k);//大概就是这个瓶子取,则相当于加入现在的瓶子里的水与新移入的水,权值是新移入的水的单位量。
				//	cout<<o<<" "<<j<<" "<<f[o][j]<<endl;
				}
			}			
		}
	}
	printf("%d",f[m][wat]);
	return 0;
}//
2022/9/26 17:50
加载中...