首页 > 代码库 > bnu 沙漠之旅

bnu 沙漠之旅

沙漠之旅

1000ms
655

“小胖要穿越一片沙漠,小胖开着一辆大吉普,小胖的吉普油耗高,吉普能放四桶油。”

这就是人人会唱的沙漠之歌~~体现了小胖拔群的聪明才智。

小胖的问题是这样的:现在需要驾车穿越一片沙漠,总的行驶路程为L。小胖的吉普装满油能行驶X距离,同时其后备箱最多能放下四桶油。在起点有N种汽油,每种汽油都有无限桶,一桶能行驶距离Ai。现在小胖想知道:能不能恰好带四桶油,再加上出发前装满的油,使得恰好能行驶L距离。

Input

第一行一个正整数T(1 <= T <= 50),表示数据的组数。

接下来T组数据,每组数据的第一行是三个整数L(1 <= L <= 1000),X(1 <= X <= L),N(1 <= N <= 1000)。

接下来N行,每行一个正整数Ai(1 <= Ai <= 1000),表示第i种汽油一桶能行驶的距离。

Output

对于每组数据输出一行,若能输出“Yes”,否则输出“No”

Sample Input

1
20 9 2
2
3

Sample Output

Yes

二维背包


#include<stdio.h>
#include<string.h>
#define N 1005
#define inf 10000000
const int M=5;
int f[N][M],a[N];
int max(int a,int b)
{
	return a>b?a:b;
}
int main()
{
	int i,j,k,l,T,n;
	int x;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d",&l,&x,&n);
		l-=x;
		for(i=0;i<=l;i++)
			for(j=0;j<M;j++)
				f[i][j]=-inf;
		f[0][0]=0;         
		for(i=0;i<n;i++)
			scanf("%d",&a[i]);
		for(i=0;i<n;i++)
		{
			for(j=a[i];j<=l;j++)
			{
				for(k=1;k<=M-1;k++)   //个数的限制,必须装四桶
				{
					for(x=1;x<=k&&x*a[i]<=j;x++)
						f[j][k]=max(f[j][k],f[j-a[i]*x][k-x]+a[i]*x);
				}
			}
		}
		if(f[l][M-1]==l)
			printf("Yes\n");
		else
			printf("No\n");
	}
	return 0;
}