当前位置:   article > 正文

P1433 吃奶酪(C++_DFS_剪枝_记忆化搜索_回溯)_c++吃奶酪

c++吃奶酪

题目描述

房间里放着 n 块奶酪。一只小老鼠要把它们都吃掉,问至少要跑多少距离?老鼠一开始在 (0,0) 点处。

输入格式

第一行一个正整数 n。

接下来每行 2 个实数,表示第i块奶酪的坐标。

两点之间的距离公式为 \sqrt{(x_1-x_2)2+(y_1-y_2)2}

输出格式

一个数,表示要跑的最少距离,保留 2 位小数。

输入输出样例

输入 #1

4
1 1
1 -1
-1 1
-1 -1

输出 #1

7.41

说明/提示

1≤n≤15。

反思

这个代码我优化过了,题解里同样用dfs+剪枝(加了个预处理)的代码我也看了,两个代码我都试了,很遗憾都没过…题解里瞅状压DP可以过,同样很遗憾,我不会,准备过段时间再学那个。

源码

#include<bits/stdc++.h>
using namespace std;
int n;
float minn = 100000.0;
class node
{
public:
	float x = 0.0, y = 0.0;
}beginn;
node a[15];
int b[15] = { 0 };//标记

float dfs(node t, int num, float l)
{
	if (l >= minn)//剪枝
		return minn;
	if (num == n)
	{
		minn = min(minn, l);
		return minn;
	}
	for (int i = 0; i < n; i++)
		if (!b[i])
		{
			b[i] = 1;//记忆
			dfs(a[i], num + 1, l + sqrt((t.x - a[i].x) * (t.x - a[i].x) + (t.y - a[i].y) * (t.y - a[i].y)));
			b[i] = 0;//回溯
		}
	return minn;
}
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i].x >> a[i].y;
	printf("%.2f",dfs(beginn, 0, 0));
	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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/木道寻08/article/detail/792390
推荐阅读
相关标签
  

闽ICP备14008679号