突然灵光一现能不能用贪心,每次去吃距离自己最近的奶酪,吃完后输出,最后只能50分,有一半wrong answer了,虽然知道这道题应该用DP,但想不通为什么不能贪心(内心隐隐约约感觉有点问题),求大神指点QWQ
https://www.luogu.com.cn/record/125128950```cpp
#include <iostream>
#include "math.h"
using namespace std;
int n;
struct node{
double x=0,y=0;
// node(double xx=0,double yy=0){
// x=xx,y=yy;
// }
}arr[20];
int vis[20];
double ans;
double dis(node a,node b){
return sqrt(pow((a.x-b.x),2)+pow(a.y-b.y,2));
}
void search(node a,int deep){
if(deep>n){
printf("%.2f",ans);
return;
}
int mini;
double mins=0xfffffffffffff;
for(int i=1;i<=n;i++){
if(!vis[i]){
double tmp=dis(a,arr[i]);
if(tmp<mins){
mini=i;
mins=tmp;
}
}
}
vis[mini]=1;
ans+=mins;
search(arr[mini],deep+1);
}
int main() {
cin>>n;
for(int i=1;i<=n;i++)cin>>arr[i].x>>arr[i].y;
search(arr[0],1);
return 0;
}