dfs75分求助
查看原帖
dfs75分求助
760998
rhn7楼主2023/11/2 21:02
#include<bits/stdc++.h>
using namespace std;
double d1,c,d2,ans=1e18,t[8],s[8];
int n;
struct Node{
	double d,p;
} a[8];
bool chk(){
	double res=0;
	for(int i=0;i<=n;i++){
		res+=t[i];
		if(res>c) return false;
		res-=s[i];
	}
	return true;
}
bool cmp(Node x,Node y){
	return x.d<y.d;
}
void dfs(int x,double sum){
	if(x>n){
		if(chk()) ans=min(ans,sum);
		return;
	}
	for(int i=0;i<=x;i++){
		t[i]+=(a[x+1].d-a[x].d)/d2;
		s[x]=(a[x+1].d-a[x].d)/d2;
		dfs(x+1,sum+(a[x+1].d-a[x].d)/d2*a[i].p);
		t[i]-=(a[x+1].d-a[x].d)/d2;
	}
}
int main(){
	cin>>d1>>c>>d2>>a[0].p>>n;
	for(int i=1;i<=n;i++) cin>>a[i].d>>a[i].p;
	a[n+1].d=d1;
	sort(a,a+n+2,cmp);
	dfs(0,0);
	if(ans==1e18) cout<<"No Solution";
	else cout<<fixed<<setprecision(2)<<ans;
	return 0;
}
2023/11/2 21:02
加载中...