#include<iostream>
using namespace std;

#define base 100000


int queen[200001][2],k,kk;
int state[200001];
int s[100],f[100],n;
int sums,sumf;

int main()
{
	scanf("%d",&n);
	int i,j;
	sums=sumf=0;
	for(i=0,j=0;i<n;i++)
	{
		scanf("%d%d",&s[j],&f[j]);
		if(s[j]<=0&&f[j]<=0)
			continue;
		else if(s[j]>0&&f[j]>0)
		{
			sums+=s[j];
			sumf+=f[j];
			continue;
		}
		j++;
	}
	queen[0][0]=sums;
	queen[0][1]=sumf;
	

	for(i=0;i<=200000;i++)
		state[i]=-200000;

	state[sums+base]=sumf;
	n=j;
	int x,y;
	kk=1;

	for(i=0;i<n;i++)
	{
		for(j=0,k=kk;j<k;j++)
		{
			x=queen[j][0]+s[i];
			y=queen[j][1]+f[i];
			if(state[x+base]==-200000)
			{
				state[x+base]=y;
				queen[kk][0]=x;
				queen[kk++][1]=y;
				continue;
			}
			if(y>state[x+base])
				state[x+base]=y;
		}
	}
	int wyh=sums+sumf;
	for(i=0;i<kk;i++)
	{
		if(queen[i][0]>=0&&queen[i][1]>=0&&queen[i][0]+queen[i][1]>wyh)
			wyh=queen[i][0]+queen[i][1];
	}
	printf("%d\n",wyh);
	return 0;
}


			
				

	

• Re:望路过的指点一下，DP题，不知道哪错了，实在看不出来，帮帮忙，先谢谢了！！ (4) need130 2006-10-31 09:00:09
• 望路过的指点一下，搜的，不知道为什么TLE实在想不出优化方法了..... (1589) fatyy 2007-03-17 22:39:48