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

struct POINT
{
	int time;
	char cor[11];
};
int maxv,average;
POINT p[101];
int M,N;
int time[11][101],count[11]={0};
char color[11][11];

int max(int a,int b)
{
	return (a>b?a:b);
}

int find(int k[],int a,int s)
{
	//int V[101][10001]={0};
	int V[101][1001]={0};
	int i,j;
	for(i=1;i<=a;i++)
		V[i][0]=0;
	for(j=1;j<=s;j++)
		V[0][j]=0;
	for(i=1;i<=a;i++)
		for(j=1;j<=s;j++)
		{
			V[i][j]=V[i-1][j];
			if(k[i]<=j)
				V[i][j]=max(V[i][j],V[i-1][j-k[i]]+k[i]);
		}
	return V[a][s];
	

}


int main()
{
	FILE *file=freopen("wash.in","r",stdin);

	while(scanf("%d%d",&M,&N),N!=0)
	{
		int i,j,sum,csum,min,result=0;
		memset(count,0,sizeof(count));

		for(i=1;i<=M;i++)
			scanf("%s",&color[i]);
		
		for(i=1;i<=N;i++)
		{
			scanf("%d%s",&p[i].time,&p[i].cor);
			for(j=1;strcmp(p[i].cor,color[j])!=0;j++);
			time[j][++count[j]]=p[i].time;
		}
		
		for(i=1;i<=M;i++)
		{
			sum=0;
			csum=0;
		//	if(count[i]==0)break;
			for(j=1;j<=count[i];j++)csum+=time[i][j];
			sum=csum;
			average=sum/2;
			//find(time[i],count[i],average);
			min=csum-find(time[i],count[i],average);
		
			result+=min;

		} 
		printf("%d\n",result);
	}
	//fclose(file);
	return 1;
}

• 把V设大点就过 (106) eminemxh 2007-04-11 23:04:54
  • Re:把V设大点就过 (120) gdufs_lin 2007-04-13 23:43:51
    • Re:把V设大点就过 (31) gdufs_lin 2007-04-13 23:44:40