【高速公路休息站充电规划】c++

来源：http://t.csdn.cn/5fIdA
题目描述
张三购买了一辆续航里程数达1000公里的某自动驾驶新能源车。 某一天车辆充满电后，需从甲城出发前往距离D公里远的乙城，全程走高速。

车载导航提示沿途有N个休息站均可提供充电服务，各休息站均可实时提供当前充电排队时间(小时)。
请协助规划时间最优的休息站充电方案，返回最短的旅行用时。

为方便计算，高速上的行驶速度固定为100公里/小时。 规划时可不必考虑保留安全续航里程数，汽车可以将电完全用光，1000公里续航的汽车按100公里/小时，可以开10个小时。每次充电时间固定为1小时，完成后电量充满。各站点充电排队时间不会变化，充电排队过程不耗电。

输入描述

第一行表示甲乙两城的距离D，单位为公里;
第二行表示沿途的休息站数量N;
第三行起，每行2个数据，分别表示休息站距离甲城的距离，以及充电排队所需时间(小时)，(各休息站按离从近到远排序)
0<=D<=1000000，D是100的整数倍
0<=N<=10000

1500
4
300 2
600 1
1000 0
1200 0

输出描述

旅程总计花费的最短时间(小时)
若无法到达终点，则返回-1

16

解释:
最佳方案：只在第3个休息站(位置1000)进行充电
1500公里的行程耗时:15小时
充电排队0小时，充电1小时
最快旅程总计花费16小时

其他方案:在第2个休息站(位置600)进行充电，总计花费17小时
其他方案:在第2个休息站(位置600)和第4个休息站(位置1200)进行充电，总计花费19小时

思路

#include

using namespace std;

vector<int> power_dis;
vector<int> power_time;

unordered_map<string, int> memo;

int dp(int pow, int dis, int N) {
	// 
	if (pow >= dis) return dis / 100;
	//
	string key = to_string(pow) + "," + to_string(dis);
	cout << key << endl;
	if (memo.count(key)) return memo[key];
	int res = INT_MAX;
	int can = dis - pow;
	for (int i = 0; i < N; i++) {
		if (can > power_dis[i]) continue;
		if (power_dis[i] == dis) continue;
		int power_d = power_dis[i];
		int power_t = power_time[i];
		if (dp(1000, power_d, N) == -1) continue;
		int tmp = (dis - power_d) / 100 + power_t + 1 + dp(1000, power_d, N);
		res = min(res, tmp);
	}
	if (res == INT_MAX) res = -1;
	memo[key] = res;
	return res;
}


int main() {
	int D, n;
	cin >> D;
	cin >> n;
	power_dis.resize(n);
	power_time.resize(n);
	for (int i = 0; i < n; i++) cin >> power_dis[i] >> power_time[i];
	// base case
	for (int i = 0; i < n; i++) power_dis[i] = D - power_dis[i];
	cout << dp(1000, D, n);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45