我觉着这是用转化的想法写的,但还是超时.请高人指点

#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();
}

• 建议写成递归的形式，自己维护栈很容易乱 (2006) frkstyc 2005-05-28 02:47:38
  • 自己写的应该更快才是，是不是算法有错或出死循环了？ (0) 00403022 2005-05-28 09:29:06
    • 出不了答案多快都没用 (0) frkstyc 2005-05-28 10:59:48
      • 自己写的栈效率不高的 (0) TN 2005-05-28 11:37:04
• 受别人的贴的启发,hawk能不能告诉我RUNID477559是大数据超时还是出现了死循环? (2006) 00403022 2005-05-28 13:52:05
  • ft... (0) 00448264 2005-05-28 13:52:47
    • 都是“死凄凄”的runid啊 (0) 00448264 2005-05-28 13:54:19
    • 这题累计6TLE+2WA,实在是不行了. (0) 00403022 2005-05-28 13:54:26
  • 这个不容易看，我不看 (0) hawk 2005-05-28 13:55:04
  • 怎么现在都流行这个...... (0) TN 2005-05-28 16:57:19
    • 我的2430真是写郁闷了调郁闷了不会找错了，现在都不知道那里错了…… (0) 00448264 2005-05-28 16:59:06
      • 不如先换道题，调整一下思维 (0) TN 2005-05-28 17:01:31
• 果然写成递归的形式就好了,不过还是有点不理解.谢谢提醒. (16) c0500403022 2005-05-28 14:37:14