Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

望路过的指点一下,搜的,不知道为什么TLE实在想不出优化方法了.....

Posted by fatyy at 2007-03-17 22:39:48 on Problem 2184
In Reply To:望路过的指点一下,DP题,不知道哪错了,实在看不出来,帮帮忙,先谢谢了!! Posted by:need130 at 2006-10-30 21:16:12

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define M 105

struct pnode
{
	int x;
	int y;
};

typedef struct pnode Cow;
Cow cow[M];
int tag[M];
void work_go();
int max;
int xsum;
int ysum;
int ncow;



int main()
{
	memset(tag,0,sizeof(tag));
	xsum=0;
	ysum=0;
	max=0;
	int number;
	Cow onecow;
	int n=0;
	scanf("%d",&number);
	for(int ix=0;ix<number;++ix)
	{
       scanf("%d%d",&onecow.x,&onecow.y);
	   if(onecow.x>=0&&onecow.y>=0)
	   {
		   xsum+=onecow.x;
           ysum+=onecow.y;
		   continue;
	   }//the cow of must be choose 
	   if((onecow.x+onecow.y)<0)//desert cow
		   continue;
	   if((onecow.x+onecow.y)>=0)
	   {
		   xsum+=onecow.x;
		   ysum+=onecow.y;
           cow[n].x=onecow.x*(-1);
		   cow[n].y=onecow.y*(-1);
		   n++;
	   }
	}//prework is complishment the number of 0~n cow should try 
	//int the following program;
	ncow=n;
	if(n==0||xsum>=0&&ysum>=0)
	{
		printf("%d\n",xsum+ysum);
		return 0;
	}
	else
	{
    work_go();
	printf("%d\n",max);
	return 0;
	}
	
}


void work_go()
{
	for(int ix=0;ix<ncow;++ix)
	{
		if(tag[ix]==0)
		{
			tag[ix]=1;
			xsum+=cow[ix].x;
			ysum+=cow[ix].y;
			if(xsum>=0&&ysum>=0)
			{
				if((xsum+ysum)>max)
					max=xsum+ysum;

                xsum-=cow[ix].x;
				ysum-=cow[ix].y;
				tag[ix]=0;
 				continue;
			}
			else if((xsum+ysum)<max)
			{
				xsum-=cow[ix].x;
				ysum-=cow[ix].y;
				tag[ix]=0;
				continue;
 			}
			work_go();
			xsum-=cow[ix].x;
			ysum-=cow[ix].y;
			tag[ix]=0;
		}
	}
}



Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator