> #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;
> }

• Re:友情帮顶 (0) MasterLuo 2008-11-07 21:15:16
• 我顶一个。。。DP。。。 (19) xujiaming 2008-11-13 14:22:47