3211.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:3211  User Id:fzk 
Memory:200K  Time:140MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <vector>
#include <string>
#include <set>
using namespace std;

vector<int> v[10];
string color[10];
set<int> s;

int main( ) {
	int n, m, i, j, ans, sum, t, best;
	char w[100];
	while( scanf( "%d%d", &m, &n ) == 2 && ( n || m ) ) {
		
		for( i=0; i<m; i++ ) {
			scanf( "%s", w );
			color[i] = w;
			v[i].clear( );
		}

		for( i=0; i<n; i++ ) {
			scanf( "%d %s", &t, w );
			for( j=0; j<m; j++ )
				if( color[j] == w )
					break;
			v[j].push_back( t );
		}
		
		set<int>::reverse_iterator it;
		ans = 0;

		for( i=0; i<m; i++ ) {
			s.clear();
			s.insert( 0 );
			sum = 0;

			for( j=0; j<v[i].size(); j++ ) {
				for( it = s.rbegin(); it != s.rend(); it++ ) {
					if( s.find( t=*it+v[i][j] ) == s.end() )
						s.insert( t );
				}
				sum += v[i][j];
			}

			best = sum;

			for( it = s.rbegin(); it != s.rend(); it++ ) {
				t = *it;
				if( sum - t > t )
					t = sum - t;
				if( best > t )
					best = t;
			}
			ans += best;
		}

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