我用的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;
}

• 直接枚举都能过 (1636) huangkun 2007-10-02 15:29:33
  • 郁闷啊，比赛时用没用G++,到最后还是TLE；G++才300多ms啊。。。 (0) Chojin 2007-10-02 15:35:02