使用dfs的解题方法如下(和上次一样,只不过注释改了一下)
查看原帖
使用dfs的解题方法如下(和上次一样,只不过注释改了一下)
1641729
caiqt楼主2025/8/4 23:16
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
double cos[15] = {}, dis[15] = {}, b[15] = {}, c, d, d2, ans = 1e9;
//cos表示第i个加油站每升油花多少钱
//dis表示每个加油站与起点的距离
//b(between)代表相邻两个油站的距离
//d表示起点到终点的距离
//c表示油箱容量(以升为单位)
//d2表示每升油能走的距离
//ans表示最终的答案(最少花费)

int n;
bool flag = false;

void dfs(int step, double cur, double mo)
{
    // step表示当前走到第几个加油站
    // cur表示当前油箱内剩下的油量(以升为单位)
    // mo代表共用多少钱
	if(step > n)
	{
		ans = min(ans, mo); // 更新答案
		flag = true; // 标记是否有答案
		return;
	}
	if(c*d2 < b[step]) return;
    //边界条件
	double sum = 0;
    // 用于累加:到下一个加油站需要走多少路程
	for(int i = step; i <= n; i++)
	{
		sum += b[i]; // 累加
		if(c*d2 < sum) break; // 不能继续累加,终止循环
		dfs(i+1, c-sum/d2, mo + (c-cur)*cos[step]); // 加满油
                 
		dfs(i+1, 0, mo + max<double>(0, cos[step]*sum/d2 - cos[step]*cur));
        // 若油量足够,不加油;否则加到刚刚好能到达下一个加油站
	}
}

int main()
{
  	cin >> d >> c >> d2 >> cos[0] >> n;
  	for(int i = 1; i <= n; i++)
  	{
  		cin >> dis[i] >> cos[i];
  	}
    sort(dis+1, dis+n+1);
    for(int i = 1; i <= n; i++)
    {
      b[i-1] = dis[i] - dis[i-1];
      // 计算相邻加油站距离
    }
  	b[n] = d-dis[n];
    // 最后一个加油站与终点的间隔
  	dfs(0, 0, 0);
  	if(flag == true) printf("%.2lf", ans);
    // 判断是否有答案
  	else printf("No Solution");
  	return 0;
}
2025/8/4 23:16
加载中...