#include<iostream>
using namespace std;
/*最优化剪枝：如果当前搜到的s+f的值加上后面最多能达到的s+f的值小于已经搜得的最大值，就退出；
可行性剪枝：如果当前搜到的s(或f)值＜0，那么如果s(或f)加上后面最多能得到的s(或f)值＜0，就退出。*/
struct point
{
	int x,y;
};
int max;
int ms,mx,my;
point p[101];
int mins[101],minx[101],miny[101];
int j;

int cmp(const void *a, const void *b)
{
	return((*(point *)b).x+(*(point *)b).y)-((*(point *)a).x+(*(point *)a).y);
}

void dfs(int i,int s,int x,int y)//i表示搜到第几点。
{
	if(s>max&&x>=0&&y>=0)
		max=s;
	if(i==j)
		return ;
	if(s+mins[i]<max)//剪枝
		return ;
	if(x<0&&x+minx[i]<0)//剪枝
		return ;
	if(y<0&&y+miny[i]<0)//剪枝
		return ;

	dfs(i+1,s,x,y);
	dfs(i+1,s+p[i].x+p[i].y,x+p[i].x,y+p[i].y);
}
	
main()
{

	int i,k,n,a,b;
    cin>>n;
	j=0;
	max=0;
	ms=0;mx=0;
	my=0;
	for(i=0;i<n;i++)
	{
		cin>>a>>b;
		if(a>=0&&b>=0&&a+b>0)
		{
			mx+=a;
			my+=b;
			ms=ms+a+b;
		}
		else if(a+b>0)
		{
			p[j].x=a;
			p[j].y=b;
			j++;
		}
	}
    qsort(p, j, sizeof(point), cmp);
    mins[j-1]=p[j-1].x+p[j-1].y;//求后面最多能达到的s+f的值，和后面最多能得到的s(或f)值
	if(p[j-1].x>0)
		minx[j-1]=p[j-1].x;
	else
		minx[j-1]=0;
	if(p[j-1].y>0)
    	miny[j-1]=p[j-1].y;
	else
		miny[j-1]=0;
	for(k=j-2;k>=0;k--)
	{
		if(p[k].x>0)
			minx[k]=p[k].x+minx[k+1];
		else
			minx[k]=minx[k+1];
		if(p[k].y>0)
			miny[k]=p[k].y+miny[k+1];
		else
			miny[k]=miny[k+1];
		mins[k]=p[k].x+p[k].y+mins[k+1];
	}
	dfs(0,ms,mx,my);
	cout<<max<<endl;
	return 0;
}

• Re:是WA，高手麻烦指点一下... (1628) luckystar 2007-08-27 13:13:53
  • 改了一下，超时了，不知怎样剪枝了。高手麻烦看一下。。。 (1603) luckystar 2007-08-27 13:15:19