当前位置：首页 > article >正文

D - Laser Marking

article 2024/10/6 12:45:25

题目链接：

D - Laser Marking (atcoder.jp)

题目描述：

大致意思：

从(0, 0) 出发，然后要进行n段激光印刷，每一段都是以一端为起点开始进行激光印刷，以另一端为终点，而且不进行激光和进行激光时候的速度是不一样的，问你完成n项任务最少需要多少时间？

样例输入：

3 2 1
1 3 2 1
0 2 0 0
3 0 2 0

样例输出：

6.44317475868633722080

样例解释：

分析：

首先：这n段的顺序是什么？这个可以用c++自带的next_permutation进行枚举这n段的顺序

其次：当我来到这一段的时候，我从哪里开始入手呢？是(A, B)还是(C, D)呢？去搜索，也就是dfs两段

dfs里面的参数 len: 当前枚举到哪一段了？sum：现在消耗了多少时间了？nowX和nowY分别代表当前的(x, y), 为什么要去记录nowX和nowY呢？因为记录这个是为了计算到下一个的开始点(端口)需要的距离。

当然也是可以去剪一下枝的，也就是如果当前的sum比我的ret(答案)大，就没有枚举下去的必要了(return)。

代码：

#include<bits/stdc++.h>
#define int long long

using namespace std;

int n;
double ret = 100000000;
int s, t;
int tt[20];

struct ty {
	int a, b, c, d;
};
ty p[20];
// 先去排序 走的是哪些 
// 然后从哪走
void dfs(int len, double sum, int nowX, int nowY) {
	if(sum > ret) {
		return ;
	}
	if(len > n) {
		ret = min(ret, sum);
		return ;
	}

	int pos = tt[len]; 
	double sumT = 0;
	sumT += sqrt(pow((p[pos].a - nowX), 2) + pow((p[pos].b - nowY), 2)) / s;
	sumT += sqrt(pow((p[pos].c - p[pos].a), 2) + pow(p[pos].d - p[pos].b, 2) ) / t;
	dfs(len + 1, sum + sumT, p[pos].c, p[pos].d);
	
	sumT = 0;
	sumT += sqrt(pow(p[pos].c - nowX, 2) + pow(p[pos].d - nowY, 2)) / s;
	sumT += sqrt(pow((p[pos].c - p[pos].a), 2) + pow(p[pos].d - p[pos].b, 2) ) / t;
	// 从哪段开始走
	dfs(len + 1, sum + sumT, p[pos].a, p[pos].b); 
} 

signed main() {
	cin >> n >> s >> t;
	
	for(int i = 1; i <= n; i ++ ) {
		tt[i] = i;
	}
	for(int i = 1; i <= n; i ++ ) {
		cin >> p[i].a >> p[i].b >> p[i].c >> p[i].d;
	}	
	
	do {
		dfs(1, 0, 0, 0);
	}while(next_permutation(tt + 1, tt + n + 1));
	
		
	printf("%.20lf\n", ret);	
	return 0;
}