dfs做法,最后一个点wa了,求助大佬们,着急着急,在线等
查看原帖
dfs做法,最后一个点wa了,求助大佬们,着急着急,在线等
35667
会唱歌的石榴楼主2023/10/17 10:18
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
double dis,con,disres,pristart;
double ans = 999999999,tot = 0;
int point = 0,n;
double d[8],p[8];
void dfs(int x,double y,double z){
	if (z >= dis){
		ans = min(tot,ans);
		point = 1;
		return;
	}
	if(tot >= ans) return; 
	for (int i = x + 1; i <= n + 1; ++i){
		if (d[i] - z <= disres * y){  //有选择权 
			dfs(i,y - (d[i] - z) * disres,d[i]);   //一点不加,直接溜溜球 
			tot += (con - y) * p[x];
			dfs(i,con - (d[i] - z) / disres,d[i]);
			tot -= (con - y) * p[x];  //加满油 
		/*	double needweightplus = (d[i] - z) / disres;
			tot += needweightplus * p[x];
			dfs(i,y + needweightplus - (d[i] - z) / disres,d[i]);
			tot -= needweightplus * p[x];*/
		}else{  //没有选择权 
			if (disres * con + z >= d[i]){  //加满 
				tot += (con - y) * p[x];
				dfs(i,con - (d[i] - z) / disres ,d[i]);
				tot -= (con - y) * p[x];   //正好加到下一站 
				double needweight = (d[i] - z) / disres;
				tot += needweight * p[x];
				dfs(i,y,d[i]);
				tot -= needweight * p[x];
			}
		}
	}
}
int main(){
	scanf("%lf%lf%lf%lf%d",&dis,&con,&disres,&pristart,&n);  //距离,油箱含量,每升油能走的,花的钱,多少站 
	for (int i = 1;i <= n; ++i)
		scanf("%lf%lf",&d[i],&p[i]);
	d[0] = 0; p[0] = pristart; 
	d[n + 1] = dis; p[n + 1] = 999999999;
	dfs(0,0,0); //现在走了z,这是在第x站,手里有y的油,对第x站进行决策 
	if (!point) printf("No Solution");
	else printf("%.2f",ans);
}
2023/10/17 10:18
加载中...