2065995_ac_46ms_400k.c

北大大牛代码 1240道题的原代码 超级权威

# include <stdio.h>
# include <string.h>
# include <stdlib.h>
int m, n;
struct node
{
	char color[11];
	int a[100];
	int p;
	int sum;
}cloth[10];

int dp(int n)
{
	int flag[100001];
	int half, i, j, max;

	memset(flag,0,sizeof(flag));
	flag[0] = 1;
	max = 0;
	half = cloth[n].sum/2;
	for(i = 0; i < cloth[n].p; i++)
		for(j = half-cloth[n].a[i]; j >= 0; j--)
			if(flag[j])
			{
				flag[j+cloth[n].a[i]] = 1;
				if(j+cloth[n].a[i]>max)
					max = j+cloth[n].a[i];
				if(max==half)
					return cloth[n].sum-half;
			}
	return cloth[n].sum-max;
}

void input()
{
	int i, j, num;
	int sum;
	char tmp[11];

	while(scanf("%d%d",&m,&n)==2&&(m||n))
	{
		for(i = 0; i < m; i++)
		{
			scanf("%s",cloth[i].color);
			cloth[i].p = 0;
			cloth[i].sum = 0;
		}
		for(i = 0; i < n; i++)
		{
			scanf("%d%s",&num,tmp);
			for(j = 0; j < m; j++)
			{
				if(strcmp(tmp,cloth[j].color)==0)
				{
					cloth[j].a[cloth[j].p] = num;
					cloth[j].sum += num;
					cloth[j].p++;
					break;
				}
			}
		}
		sum = 0;
		for(i = 0; i < m; i++)
		{
			if(cloth[i].p!=0)
				sum += dp(i);
		}
		printf("%d\n",sum);
	}
}

int main()
{
	input();
	return 1;
}