求助,只有70分,没用状态压缩
  • 板块P1433 吃奶酪
  • 楼主nob_lz
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/10/5 12:59
  • 上次更新2024/10/5 15:15:58
查看原帖
求助,只有70分,没用状态压缩
1416590
nob_lz楼主2024/10/5 12:59

我的思路是从原点出发,找到一个离它最近的点,再把最近的那个点作为起点,再找到离起点最近的点,这个思路到底哪里有问题?。。。

#include<bits/stdc++.h>
using namespace std;

int n;
double x[20],y[20];
double dp[205];
bool vis[25];
int idx;
double sum;

double two_dis(double x1,double y1,double x2,double y2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

void solve(){
    for(int i=0;i<n;i++){
        int t=idx;
        vis[idx]=true;
        dp[i]=1e9;
        for(int j=0;j<=n;j++){
            if(!vis[j]){
                if(two_dis(x[t],y[t],x[j],y[j])<=dp[i]) idx=j;
                dp[i]=min(dp[i],two_dis(x[t],y[t],x[j],y[j]));
            }
        }
    }
}

int main(){
    cin>>n;
    x[0]=0;
    y[0]=0;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
    }
    solve();
    for(int i=0;i<n;i++){
        sum+=dp[i];
    }
    printf("%.2lf",sum);
}
2024/10/5 12:59
加载中...