Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
WA啊, 求助!! 简单的01背包问题, 大家帮忙看下 ,谢谢哈#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:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator