#include<stdio.h>
#include<string.h>
bool flag[210000];
int f[210000];
const int K=100000;
int left,right;
void ZeroOne_Pack1(int cost ,int weight)
{
	int i,ti,tv;
	for(i=left;i<=right;++i)
	{
		if(flag[i]&&f[(ti=i+cost)]<(tv=f[i]+weight))
		{
			flag[ti]=1;
			f[ti]=tv;
		}
	}
	left-=cost;
}
void ZeroOne_Pack2(int cost , int weight)
{
	int i,ti,tv;
	for(i=right;i>=left;--i)
	{
		if(flag[i]&&f[(ti=i+cost)]<(tv=f[i]+weight))
		{
			flag[ti]=1;
			f[ti]=tv;
		}
	}
	right+=cost;
}
int main()
{
	int i,j;
	int S,F,N;
	while(scanf("%d",&N)!=-1)
	{
		//memset(f,0,sizeof(f));
		memset(f,0xbf,sizeof(f));
		memset(flag,0,sizeof(flag));
		f[K]=0;flag[K]=1;
		left=right=K;
		for(i=0;i<N;++i)
		{
			scanf("%d%d",&S,&F);
			if(S<0&&F<0)continue;
			if(S<0)
				ZeroOne_Pack1(S,F);//front to rear
			else
				ZeroOne_Pack2(S,F);//rear to front
		}
		int Max=0;
		for(i=left;i<=right;++i)
		{
			if(!flag[i])continue;
			if(i<K)continue;
			if(f[i]<0)continue;
			if(f[i]+i>Max)
				Max=f[i]+i;
		}
		printf("%d\n",Max-K);
	} 
	return 0;
}

• 粘错了 我把原始的代码粘上去了 同上问 (1073) 421162789 2009-08-03 20:27:03