> 我用的DFS,觉得没有问题啊..没有TL,老是WA不知道还有什么情况没有考虑到的啊......
> 谢谢了..给数据或者帮我看看程序:)麻烦了,先谢过:)
> #include <iostream>
> #include <iomanip>
> 
> using namespace std;
> 
> long n,now[11],best[11];
> double ans,now_ans,a[11],b[11],s[11],d;
> bool pd[11];
> 
> void get_ans(long x)
> {
> 	long i;
> 	double temp,tempnow;
> 	
> //	cout<<x<<endl;
> 	if (x==n+1) {
> //		        cout<<now_ans<<endl;
> //		        cout<<ans<<endl;
> //		        system("pause");
> 		        if (now_ans>ans) {
> 								   ans=now_ans;
> 								   for (i=0;i<=n;i++) best[i]=now[i];
> 							     }
> 				}
> 	else {
> 		   for (i=1;i<=n;i++)
> 		   if (pd[i]==false)
> 		   {
> 				
> 				now[x]=i;
> 				if (d<a[i]) temp=0; else
> 				if (d<b[i]&&a[i]<=d) temp=(d-a[i])/(b[i]-a[i]);
> 				                     else temp=1;
> 				tempnow=now_ans;
> 				now_ans=now_ans*temp;
> //				cout<<x<<":"<<i<<endl;
> //				cout<<a[i]<<"/"<<d<<"/"<<b[i]<<endl;
> //				cout<<temp<<"!!"<<now_ans<<endl;
> 				d=d+s[i];
> 				pd[i]=true;
> 				get_ans(x+1);
> 				pd[i]=false;
> 				d=d-s[i];
> 				if (now_ans==0) now_ans=tempnow;
> 				           else now_ans=now_ans/temp;
> 				now[x]=0;
> 		   }
> 		 }
> }
> 
> int main()
> {
> 	long i;
> 	
> 	//init;
> 	cin>>n>>d;
> 	for (i=1;i<=n;i++) cin>>a[i]>>b[i]>>s[i];
> 	now[0]=0;
>     for (i=1;i<=n;i++) pd[i]=false;
>     
> 	//main;
> 	now_ans=1.000;ans=0.000;
> 	get_ans(1);	
> 	
> 	//print;
> 	cout<<setiosflags(ios::fixed)<<setprecision(3)<<ans<<endl;
> 	for (i=1;i<=n-1;i++) cout<<best[i]<<" ";
> 	cout<<best[n]<<endl;
> 	system("pause");
> 	return 0;
> }

• 郁闷啊，比赛时用没用G++,到最后还是TLE；G++才300多ms啊。。。 (0) Chojin 2007-10-02 15:35:02