Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

直接枚举都能过

Posted by huangkun at 2007-10-02 15:29:33 on Problem 3413
In Reply To:救命啊~~~~~~~~~一直是WA!!! Posted by:trueshlqsh at 2007-10-02 14:36:45
> 我用的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;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator