3331406_wa.c

来自「北大大牛代码 1240道题的原代码 超级权威」· C语言 代码 · 共 68 行

#include <stdio.h>
#include <string.h>

int value[6];
int num[101];

void dp()
{
	int i, j, max;
	double tot;

	memset(num,-1,sizeof(num));
	num[0] = 0;
	for (i = 0; i < 101; i++)
	{
		if (num[i]!=-1)
		{
			for (j = 0; j < 6; j++)
			{
				if (i+value[j]<101&&(num[i+value[j]]==-1||num[i+value[j]]>num[i]+1))
				{
					num[i+value[j]] = num[i]+1;
				}
			}
		}
	}
	for (i = 1; i < 101; i++)
	{
		for (j = i+1; j < 101; j++)
		{
			if (num[j]==-1||num[j-i]==-1)
			{
				continue;
			}
			if (num[i]==-1||num[i]>num[j]+num[j-i])
			{
				num[i] = num[j]+num[j-i];
			}
		}
	}
	max = 0;tot = 0;
	for (i = 1; i < 101; i++)
	{
		tot += num[i];
		if (num[i] > max)
		{
			max = num[i];
		}
	}
	printf("%.2lf %d\n",tot/100.0,max);
}

int main()
{
	int i, cas;

	scanf("%d",&cas);
	while (cas-- > 0)
	{
		for (i = 0; i < 6; i++)
		{
			scanf("%d",&value[i]);
		}
		dp();
	}
	return 0;
}