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 mgyrider at 2014-10-11 00:13:39 on Problem 3211
```#include<iostream>
#include<cstdio>
#include<string>
#include<map>
#include<vector>
using namespace std;

int dp[60000];
int sum[10];
map<string,int> color;

int main()
{
int M,N;
while(~scanf("%d%d",&M,&N),M+N)
{
vector<int> V[10];
for(int i=0;i<M;i++)
{
string c;
cin >> c;
color[c] = i;
}
memset(sum,0,sizeof sum);
while(N--)
{
int v,x;
string c;
cin >> v >> c;
x = color[c];
V[x].push_back(v);
sum[x] += v;
}
int ans = 0;
for(int c=0;c<M;c++)
{
int s = sum[c];
memset(dp,0,sizeof dp);
for(int i=0;i<V[c].size();i++)
for(int j=s;j>=V[c][i];j--)
dp[j] = max(dp[j],dp[j-V[c][i]]+V[c][i]);

for(int i=(s+1)/2;i<=s;i++)
if(dp[i]==i)
{
ans += i;
//	printf("dp[%d] = %d\n",i,dp[i]);
break;
}

}
printf("%d\n",ans);

}
} ```

Followed by: