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

受别人的贴的启发,hawk能不能告诉我RUNID477559是大数据超时还是出现了死循环?

Posted by 00403022 at 2005-05-28 13:52:05 on Problem 2184
In Reply To:求救,2184 Posted by:00403022 at 2005-05-28 02:40:20
> 我觉着这是用转化的想法写的,但还是超时.请高人指点
> 
> #include<iostream.h>
> 
> struct cows
> {
>     short s,f;
> };
> struct cows cow[100];
> short n,num;
> 
> void main()
> {
>     //fstream cin;
>     //cin.open("input.txt",ios::in);
>     cin>>num;
>     n=0;
>     short xh1;
>     int ts,tf;
>     ts=0;
>     tf=0;
>     for (xh1=0;xh1<num;xh1++)
>     {
>       cin>>cow[n].s>>cow[n].f;
>       if (cow[n].s>=0 && cow[n].f>=0)
>       {
> 	 ts+=cow[n].s;
> 	 tf+=cow[n].f;
> 	 continue;
>       }
>       if (cow[n].s<=0 && cow[n].f<=0) continue;
>       if (cow[n].s+cow[n].f>=0)
> 	if (cow[n].s>0)
> 	{
> 	  ts+=cow[n].s;
> 	  tf=tf+cow[n].f;
> 	  cow[n].s*=-1;
> 	  cow[n].f*=-1;
> 	  n++;
> 	}
> 	else
> 	{
> 	  ts=ts+cow[n].s;
> 	  tf+=cow[n].f;
> 	  cow[n].s*=-1;
> 	  cow[n].f*=-1;
> 	  n++;
> 	}
>       else n++;
>     }
>     //读入完成 
>     if (n==0)
>     {
>       cout<<ts+tf<<endl;
>       return;
>     }
>     if (ts>=0 && tf>=0)
>     {
>       cout<<ts+tf<<endl;
>       return;
>     }                     //先把一些情况输出
>     //prework finished
>     short cho[100];
>     short top;
>     int MAX=0;
>     top=0;
>     cho[top]=-1;
>     while (top>=0)         //找去掉那些奶牛可使问题有解
>     {
>       if (top==n)
>       {
> 	top--;
> 	ts=ts-cow[cho[top]].s;
> 	tf=tf-cow[cho[top]].f;
> 	continue;
>       }
>       cho[top]++;
>       if (cho[top]==n)
>       {
> 	top--;
> 	ts=ts-cow[cho[top]].s;
> 	tf=tf-cow[cho[top]].f;
> 	continue;
>       }
>       ts+=cow[cho[top]].s;
>       tf+=cow[cho[top]].f;
>       if (ts>=0 && tf>=0)        //剪枝条件1,有可行解
>       {
> 	if (MAX<ts+tf) MAX=ts+tf;
> 	ts=ts-cow[cho[top]].s;
> 	tf=tf-cow[cho[top]].f;
> 	continue;
>       }
>       if (ts+tf<MAX)             //剪枝条件2,不可能有更好的解
>       {
> 	ts=ts-cow[cho[top]].s;
> 	tf=tf-cow[cho[top]].f;
> 	continue;
>       }
>       top++;
>       cho[top]=cho[top-1];
>     }
>     cout<<MAX<<endl;
>    // cin.close();
> }

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