P1016dfs做法75pts求调
查看原帖
P1016dfs做法75pts求调
511811
崛起的滑稽楼主2024/5/12 22:13
#include <bits/stdc++.h>
using namespace std;
double d1,c,d2,p,ans=INT16_MAX*1.0f;
int n;
bool r=false;
struct Node{
	double d,v;
}a[10];
void dfs(int x,int y,double s){
	if(x==n+1){
		ans=min(ans,s);
		r=true;
		return ;
	}
	for(int i=x+1;i<=n+1;++i){
		if(a[i].d-a[x].d>c*d2){
			break;
		}
		double tmp=(a[i].d-a[x].d)/d2;//前往目标站点需要的油量
		dfs(i,c-tmp,s+a[x].v*(c-y));//加满
		dfs(i,0,s+max((double)0,tmp*a[x].v-y*a[x].v));
	}
}
int main(){
	cin>>d1>>c>>d2>>p>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i].d>>a[i].v;
	}
	//开头结尾作为特殊站点
	a[n+1]={d1,0};
	a[0]={0,p};
	dfs(0,0.0f,0.0f);
	if(!r){//没找到答案
		cout<<"No Solution";
		return 0;
	}
	printf("%.2lf",ans);
}
2024/5/12 22:13
加载中...