Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 自己顶下,不让沉下去.... 过的了人帮看看啊

Posted by caizhicong0503 at 2008-11-05 15:44:22 on Problem 3211
In Reply To:WA啊, 求助!! 简单的01背包问题, 大家帮忙看下 ,谢谢哈 Posted by:caizhicong0503 at 2008-11-04 19:14:14
```> #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;
> }
```

Followed by: