> 我觉着这是用转化的想法写的,但还是超时.请高人指点
> 
> #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();
> }

• 自己写的应该更快才是，是不是算法有错或出死循环了？ (0) 00403022 2005-05-28 09:29:06
  • 出不了答案多快都没用 (0) frkstyc 2005-05-28 10:59:48
    • 自己写的栈效率不高的 (0) TN 2005-05-28 11:37:04