【解题报告】洛谷P1433 吃奶酪
题目链接
https://www.luogu.com.cn/problem/P1433
思路
这道题目出现在搜索的题单里，我就当搜索做了吧
然后就直接做了
发现超时一个点
怎么办
玄学优化，当递归次数超过某个值的时候直接返回当前最优解
似乎是参数的选择是凭借运气吧
大概似乎貌似好像
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <ctime>
using namespace std;
const int maxn=20;
int n,cnt;
double ans=999999.0;
double x[maxn],y[maxn],dis[maxn][maxn];
bool vis[maxn]={false};
double dist;
double get(int i,int j)
{
if(dis[i][j]!=0) return dis[i][j];
return dis[i][j]=dis[j][i]=(double)(sqrt(1.0*(x[i]-x[j])*(x[i]-x[j])+1.0*(y[i]-y[j])*(y[i]-y[j])));
}
void dfs(int now,int dep)
{
cnt++;
if(cnt>=25000000)
{
printf("%.2lf",ans);
exit(0);
}
if(dist+0.00001>ans) return ;
if(dep>n)
{
ans=min(ans,dist);
return ;
}
for(int i=1;i<=n;i++)
{
if(vis[i]) continue;
vis[i]=true;
double add=get(now,i);
dist+=add;
if(dep==n-1)
dfs(i,dep+2);
else
dfs(i,dep+1);
dist-=add;
vis[i]=false;
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>x[i]>>y[i];
dfs(0,0);
printf("%.2lf\n",ans);
return 0;
}
|
