| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
望路过的指点一下,搜的,不知道为什么TLE实在想不出优化方法了.....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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator