2184.txt

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

#include <stdio.h>
#include <memory.h>
#include <algorithm>
#include <functional>
using namespace std;

bool mem[200100],*sign = mem+100000;
int mem2[200100],*ans = mem2+100000;

typedef pair<int,int> node;
node c[100];
int n;

node mem3[2][100000],*s = mem3[0], *t = mem3[1];
int sn,tn;

int main()
{
	int i, j, n, k, h, m, v;

	scanf( "%d", &n );

	for( i=0; i<n; i++ )
		scanf( "%d %d", &c[i].first, &c[i].second );

	memset( sign-1000*n-5, 0, sizeof(bool) * ( 1000*2*n+10 ) );

	sign[0] = true;
	ans[0] = 0;
	sn = 0;

	s[sn].first = 0;
	s[sn].second = 0;
	sn++;

	for( i=0; i<n; i++ )
	{
		for( m=sn, j=0 ; j < m ; j++ )
		{
			h = s[j].second + c[i].second;
			k = s[j].first + c[i].first;

			if( ! sign[k] )
			{
				sign[k] = true;
				ans[k] = h;
				
				s[sn].first = k;
				s[sn].second = h;
				sn++;
			}
			else if( h > ans[k] )
			{
				ans[k] = h;

				s[sn].first = k;
				s[sn].second = h;
				sn++;
			}

		}
		
		std::merge( s, s+m, s+m, s+sn, t, greater<node>() );
		swap( t, s );

		m = sn;
		v = s[0].second;
		tn = 0;
		t[tn++] = s[0];

		for( j = 1; j<m; j++ )
		{
			if( s[j].second > v )
			{
				t[tn++] =  s[j];
				v = s[j].second;
			}
		}

		swap( t, s);
		swap( tn, sn);

		if( tn >= 100000 || sn >=100000 )
			while(1) printf( "faint\n" );
		
	}

	int answer = 0;
	
	for( i=0; i<=1000*n; i++ )
		if( sign[i] && ans[i] >=0 && i + ans[i] > answer )
			answer = i + ans[i];

	printf( "%d\n", answer );

	return 0;
}