 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| 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 | |||||||||
哪位大侠过了的帮忙看看我用深搜＋剪枝怎么还limited time exceed？哪位大侠帮忙看看（随手写的，很乱，呵呵）
#include<iostream.h>
#include<math.h>
#include<stack>
using namespace std;
struct subnod{
int nextnode;
int cheaperprice;
subnod *nextsub;
};
struct node{
int price;
int level;
int numofsub;
subnod *firstsub;
};
node nodearray[101];
inline bool test(stack<subnod*> &a,int m,int d)
{int maxlev=d;
int minlev=d;
subnod *b;
stack<subnod*> c;
while(a.empty()==false)
{b=a.top();
a.pop();
c.push(b);
if(nodearray[b->nextnode].level>maxlev)
maxlev=nodearray[b->nextnode].level;
if(nodearray[b->nextnode].level<minlev)
minlev=nodearray[b->nextnode].level;
}
while(!c.empty())
{b=c.top();
c.pop();
a.push(b);
}
if((maxlev-minlev)>m)
return false;
return true;
}
void main()
{int M;
int N;
cin>>M;
cin>>N;
if(N<0||N>100)
return;
int i=1;
int j=1;
subnod *temp;
subnod *tempnext;
for(;i<=N;i++)
{cin>>nodearray[i].price;
cin>>nodearray[i].level;
cin>>nodearray[i].numofsub;
if(nodearray[i].numofsub!=0)
nodearray[i].firstsub=new subnod;
else nodearray[i].firstsub=NULL;
temp=nodearray[i].firstsub;
for(j=1;j<=nodearray[i].numofsub;j++)
{cin>>temp->nextnode;
cin>>temp->cheaperprice;
if(j==nodearray[i].numofsub)
tempnext=NULL;
else
tempnext=new subnod;
temp->nextsub=tempnext;
temp=tempnext;
}
}
int tempprice=0;
int tempmin=nodearray[1].price;
int max=nodearray[1].level;
stack<subnod*> astack;
if((temp=nodearray[1].firstsub)!=NULL)
{astack.push(temp);
while(temp!=NULL)
{if(test(astack,M,max))
{tempprice+=(temp->cheaperprice);
if(tempprice+nodearray[temp->nextnode].price<tempmin)
tempmin=tempprice+nodearray[temp->nextnode].price;
temp=nodearray[temp->nextnode].firstsub;
if(temp!=NULL&&tempprice<tempmin)
astack.push(temp);
else
while(temp==NULL)
{ if(!astack.empty())
{
temp=astack.top();
astack.pop();
tempprice-=temp->cheaperprice;
temp=temp->nextsub;
if(temp!=NULL)
astack.push(temp);
}
else
{cout<<tempmin;
return;
}
}
}
else
{astack.pop();
temp=temp->nextsub;
if(temp!=NULL&&tempprice<tempmin)
astack.push(temp);
else
while(temp==NULL)
{ if(!astack.empty())
{
temp=astack.top();
astack.pop();
tempprice-=temp->cheaperprice;
temp=temp->nextsub;
if(temp!=NULL)
astack.push(temp);
}
else
{cout<<tempmin;
return;
}
}
}
}
}
cout<<tempmin;
}
Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
