#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

struct WashClothes
{
	int time;
	string color;
};

bool cmp(WashClothes a, WashClothes b)
{
	if(a.color < b.color) return 1;
	else if(a.color > b.color) return 0;
	return a.time < b.time;
}

int Bag(vector<int> &p)
{
	if(p.size() == 0) return 0;
	else if(p.size() == 1) return p[0];
	bool ok[300001];
	memset(ok,0,sizeof(ok));
	ok[p[0]] = 1;
	int Max = p[0];
	int sum = p[0];
	for(int i = 1; i< p.size(); ++i)
	{
		//ok[p[i]] = 1;
		int M = Max;
		sum += p[i];
		if(p[i] > M) M = p[i];
		for(int j = 1; j<= Max; ++j)
		{
			if(ok[j] && (j+p[i])<= sum)
			{
				ok[j+p[i]] = 1;
				if(j+p[i] > M) M = j+p[i];
			}
		}
		ok[p[i]] = 1;
		
		Max = M;
	}
	int ret = max(p[0],sum-p[0]);
	for(int i = 0; i<= Max; ++i)
	{
		if(ok[i])
		{
			if(ret > max(i, sum-i))
			{
				ret = max(i, sum-i);
			}
		}
	}
	return ret ;
}

int main()
{
	int n,m;
	while(scanf("%d %d",&n,&m)) {
		if( n == 0 && m == 0) break;
		char ss[1000];
		for(int i = 0; i< n; ++i) scanf("%s",&ss);
		WashClothes wc;
		vector<WashClothes> Clothes;
		for(int i = 0; i< m; ++i)
		{
			cin >> wc.time >> wc.color;
			//scanf("%d %s",&wc.time,&ss);
			//wc.color = ss;
			Clothes.push_back(wc);
		}
		sort(Clothes.begin(), Clothes.end(), cmp);
		vector<int> p;
		string color = Clothes[0].color;
		p.push_back(Clothes[0].time);
		int ret = 0;
		for(int i = 1; i< Clothes.size(); ++i)
		{
			if(Clothes[i].color != color)
			{
				ret += Bag(p);
				p.clear();
				p.push_back(Clothes[i].time);
				color = Clothes[i].color;
			}
			else p.push_back(Clothes[i].time);
		}
		ret += Bag(p);
		printf("%d\n",ret);
		//cout << ret << endl;
	}
	return 0;
}

• 自己顶下,不让沉下去.... 过的了人帮看看啊 (2004) caizhicong0503 2008-11-05 15:44:22
• 牛人帮看看啊,Come On!! (2004) caizhicong0503 2008-11-07 18:31:09
  • Re:友情帮顶 (0) MasterLuo 2008-11-07 21:15:16
  • 我顶一个。。。DP。。。 (19) xujiaming 2008-11-13 14:22:47