自动搬运

查看原文

来自洛谷，原作者为

	Okimoto *  *

搬运于2025-08-24 21:22:09，当前版本为作者最后更新于2020-09-22 18:16:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P1180

原本以为是一道朴素的深搜+模拟，然鹅……

算法：深搜+模拟+题意纠正

本题除读题和理解题意之外难度极低……

（题意正确的话这道题该是红/橙题）

Before AC

做题之前先纠正一下题意：

1. 在每一个停下的加油站总是将油箱加满（不是第一个）
2. 输出时将答案保留十分位。（不必四舍五入）

好了，理解清楚了题意，这道题瞬间变红题。

还有几个需要注意的点：

1. 输入是实数的，有可能是浮点数。
2. 深搜剪枝更加保险。$(n ≤ 50)$
3. 司机恰饭还要20元。
4. “不少于最大容量的一半”，即为大于等于，而不是大于。
5. 记得加上出发时加油的钱！
6. 可以把起点、终点作为一个加油站，简化问题。

别抄题解o：

// By Sublime Text 3
// P1180, by Okimoto
// No copy, pls.
#include <stdio.h>
#include <math.h>
using namespace std;
struct stn
{
	double loc;
	double prc;
};
stn gas[64];
int dis, n;
double vol, per, cst, ans;
bool flg = true;
void dfs(double ful, int loc, double sum){
	if(loc == n + 1){
		if(flg){
			ans = sum;
			flg = false;
		}
		else if(sum < ans){
			ans = sum;
		}
		return;
	}
	if((gas[loc + 1].loc - gas[loc].loc) / per > ful){
		sum += 20;
		sum += gas[loc].prc * (vol - ful);
		ful = vol;
		ful -= (gas[loc + 1].loc - gas[loc].loc) / per;
		dfs(ful, loc + 1, sum);
	}
	else if(ful < vol / 2){
		dfs(ful - (gas[loc + 1].loc - gas[loc].loc) / per, loc + 1, sum);
		sum += 20;
		sum += gas[loc].prc * (vol - ful);
		ful = vol;
		ful -= (gas[loc + 1].loc - gas[loc].loc) / per;
		dfs(ful, loc + 1, sum);
	}
	else{
		ful -= (gas[loc + 1].loc - gas[loc].loc) / per;
		dfs(ful, loc + 1, sum);
	}
}
int main(int argc, char const *argv[])
{
	scanf("%d", &dis);
	scanf("%lf %lf %lf %d", &vol, &per, &cst, &n);
	for(int i = 1; i <= n; i ++)
		scanf("%lf %lf", &gas[i].loc, &gas[i].prc);
	gas[n + 1].loc = dis;
	gas[0].loc = 0;
	dfs(vol, 0, 0);
	printf("%.1lf", ans + cst);
	return 0;
}
// 你能看到我，是我最大的心愿♥