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 897346026 at 2012-08-11 15:27:31 on Problem 3211
// POJ 3211
#include <map>
#include <vector>
#include <string>
#include <iostream>
using namespace std;

const int MAXN3211 = 100002;
const int MAXM3211 = 11;

map<string, int> colors3211;

vector<int> clothes3211[MAXM3211];
int ans3211[MAXN3211];

int main(void)
{
int i, j, k, m, n, num, sum, mid, ans;
string color;

while((cin >> m >> n) && (m || n))
{
for(i = 1; i <= m; ++i)
{
cin >> color;
colors3211[color] = i;
clothes3211[i].clear();
}
for(i = 0; i < n; ++i)
{
cin >> num >> color;
clothes3211[colors3211[color]].push_back(num);
}
memset(ans3211, 0, sizeof(ans3211));
ans = 0;
for(i = 1; i <= m; ++i)
{
for(sum = j = 0; j < clothes3211[i].size(); ++j)
sum += clothes3211[i][j];	// 第i种颜色的衣服的总时长
mid = sum >> 1;		// 平均点，使第一个人洗的时间尽量靠近该时间
// 以平均点为容量求解01背包，算出第一个的最大时间(<=mid)
for(j = 0; j < clothes3211[i].size(); ++j)
{
for(k = mid; k >= clothes3211[i][j]; --k)
if(ans3211[k - clothes3211[i][j]] + clothes3211[i][j] > ans3211[k])
ans3211[k] = ans3211[k - clothes3211[i][j]] + clothes3211[i][j];
}
ans += sum - ans3211[mid];	// 最长时间，即第二个人完成的时间
}
cout << ans << endl;
}
return 0;
}

/*
Sample Input

3 4
red blue yellow
2 red
3 blue
4 blue
6 red

3 4
red blue yellow
3 red
3 red
4 blue
4 blue

2 8
red blue
4 red
7 red
5 red
5 blue
4 red
7 blue
4 red
3 blue

0 0
Sample Output

10
7
20
*/

Followed by: