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