1973.txt

来自「北大ACM题目例程 详细的解答过程 程序实现 算法分析」· 文本 代码 · 共 58 行

#include"iostream.h"
int f[110],ft[110];
int n,m;
int t1[110],t2[110];

bool checkout(int t)
{
	int i,j,a,b;
	for(i=1;i<=m;i++)
		f[i]=-1;
	f[0]=0;

	for(j=0;j<=m;j++)
		ft[j]=f[j];

	for(i=0;i<n;i++)
	{
		for(a=0;a<=t/t1[i]&&a<=m;a++)
		{
			b=(t-t1[i]*a)/t2[i];
			for(j=0;j<=m-a;j++)
				if(f[j]>=0)
				{
					if(ft[j+a]<f[j]+b)
						ft[j+a]=f[j]+b;
				}
		}
		for(j=0;j<=m;j++)
		  f[j]=ft[j];
		if(f[m]>=m)return 1;
	}
	return f[m]>=m;
}

int main()
{
	int t,a,b,i,c;
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		for(i=0;i<n;i++)
			cin>>t1[i]>>t2[i];
		a=0;
		b=9999;
		while(a<b)
		{
			c=(a+b)/2;
			if(checkout(c))b=c;
			else a=c+1;
		}
		cout<<b<<endl;
	}
	return 0;
}