50+re
查看原帖
50+re
702659
l0k9j8h7楼主2023/10/2 10:47
#include<iostream>
#include<vector>
#include<algorithm>
		using namespace std;
#define max 100000000
#define failed "No Solution"
	struct s {
		double d, p;
	};
	vector<s> l;
	vector<pair<double, int>>cost;
double dfs(int s, double left_d/*当前剩余油量可开路程*/, double now_cost);
	bool cmp(pair<double, int> a, pair<double, int> b) {
		return a.first < b.first;

	}
	bool cmp2(s a, s b) {
		return a.d < b.d;

	}double d1, c, d2, p;
	int main() {
		double sum = max;

		int n;
		cin >> d1 >> c >> d2 >> p >> n;


		for (int i = 0; i < n; i++) {
			s a;
			cin >> a.d >> a.p;
			l.push_back(a);
			cost.emplace_back(make_pair(l[i].p, i));
		}
		if (!l.empty()) {
			stable_sort(l.begin(), l.end(), cmp2);
			if (c*d2 < l[0].d) {
				cout << failed;
				return 0;
			}
		}
		else {
			if (c*d2 < d1) {
				cout << failed;

			}
			else printf("%.2f", d1 / d2 * p);

			return 0;
		}
		if (!cost.empty())stable_sort(cost.begin(), cost.end(), cmp);
		for (int i = 0; l[i].d < c*d2; i++) {
			if (l[i].p >= p)sum = min(dfs(i, c*d2 - l[i].d, (c*d2 - l[i].d) * p / d2), sum);
			else {
				sum = min(dfs(i, 0, l[i].d * p/d2), sum);
			}
		}
		printf("%.2f", double(sum));
	}
double dfs(int s, double left_d/*当前剩余油量可开路程*/, double now_cost) {
		if (s >= l.size()) {
			if (left_d == 0)return now_cost;
			else return -1;
		}
		double cost=0x7f7f7f7f7f;
		if (s < l.size() - 1) {
			if (c * d2 < l[s + 1].d - l[s].d) {
				cout << "No Solution";
				exit(0);
			}
		}
		else if (s == l.size()) {


			if (c * d2 < d1 - l[s].d)cout << "No Solution", exit(0);
		}
		else {
			const int max_dis = min(c * d2, d1 - l[s].d),dis_per_money=d2/l[s].p;//m/l /mo*l
			
			for (int i = s + 1; i != l.size(); i++) {
				if (left_d>=l[i].d-l[s].d) {
					cost=min(cost,dfs(i, left_d - (l[i].d - l[s].d), 0));//do nothing
				}
				else {
					cost = min(cost, dfs(i, 0, (l[i].d - l[s].d-left_d) * dis_per_money));//oil_to_need
					cost = min(cost, dfs(i, max_dis - l[s].d, (max_dis - left_d) * dis_per_money));//oil to all
				}
			}
			
		}
		return now_cost + cost;
}




2023/10/2 10:47
加载中...