Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator