1882.txt

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

#define debug 0
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define NMAX 101
#define INF 10000
int anset[NMAX],alen,min;
int m[10020];
int t[NMAX];
int N,S,len;
void solve()
{
	int i,j;
	m[0]=0;
	i=1;
	while(1)
	{
		m[i]=INF;
		
		for(j=0;j<len;j++)
		{
			if(t[j]>i)
				break;
			if(m[i]>m[i-t[j]]+1)
			{
				m[i]=m[i-t[j]]+1;
			}
			
		}
		if(m[i]>S)
			break;
		i++;
	}
	i--;
	if(min<i)
	{
		min=i;
		alen=len;
		memcpy(anset,t,sizeof(t));
	}
	else if(min==i)
	{
		if(alen>len)
		{
			alen=len;
			memcpy(anset,t,sizeof(t));
		}
		else if(alen==len)
		{
			if(anset[alen-1]>t[len-1])
				memcpy(anset,t,sizeof(t));
		}
	}
}	
void output()
{
	int i;
	printf("max coverage = %d :",min);
	for(i=0;i<alen;i++)
		printf(" %d",anset[i]);
	printf("\n");
}
main()
{
#if debug 	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	int i;
	scanf("%d",&S);
	while(S)
	{
		scanf("%d",&N);
		min=-1;
		while(N--)
		{
			scanf("%d",&len);
			for(i=0;i<len;i++)
			{
				scanf("%d",&t[i]);
			}
			solve();
		
		}
		output();
		scanf("%d",&S);
	}
#if debug
	fclose(stdin);
	fclose(stdout);
#endif;
	return 1;
}