P1433 吃奶酪（DFS剪枝）

奶酪（DFS剪枝）"/>

P1433 吃奶酪（DFS剪枝）

上题目：

P1433 吃奶酪 - 洛谷 | 计算机科学教育新生态 (luogu)

看完了吗->

        进行问题分析：使用剪枝的方法（本菜菜就只会这一种方法），来降低时间复杂度进行求解，你就可以的到90分了，90分已经是我的极限了，满分方法请参考状态DP，上代码：

#include <iostream>
#include <cmath>
using namespace std;
int n;
bool vis[20];	
double a[20], b[20];	
double ans = 2222222222.0;	
double suanshi(int x, int y)
{return sqrt((a[x] - a[y]) * (a[x] - a[y]) + (b[x] - b[y]) * (b[x] - b[y]));
}void dfs(int p, double len, int m)//p
{if (len > ans)	return;//剪枝，如果长度已经比已知的大了，就终止if (m == n) {//递归到点数与题目相同时ans = len;//让ans取得最小值return;}for (int i = 1; i <= n; i++){if (vis[i]==false) {	vis[i] = true;dfs(i, len + suanshi(p, i), m + 1);vis[i] = false;}}
}int main()
{ios::sync_with_stdio(false);//加快速度，虽然在这道题里没啥用cin>>n;a[0] = 0;b[0] = 0;for (int i = 1; i <= n; i++)cin >> a[i] >> b[i];dfs(0, 0.0, 0);printf("%.2lf", ans);return 0;
}

        dfs剪枝的一个用法，加快速度，用VIS数组标记，回溯，先写到这里吧，本菜菜要午休了！