社区讨论
70pt ,不是很明白为什么会wa,和题解也对比了,求大佬调
P1433吃奶酪参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lo1ov14m
- 此快照首次捕获于
- 2023/10/23 00:34 2 年前
- 此快照最后确认于
- 2023/11/03 01:15 2 年前
CPP
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
double dp[1<<15][15];//在i状态下,最后一部到第j块奶酪
double map[25][25];
double x[1005],y[1005];
int main()
{int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lf%lf",&x[i],&y[i]);
}
memset(map,0x7f,sizeof(map));
for(int i=0;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) {
map[i][j]=0;
continue;
}
map[i][j]=sqrt( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) );
map[j][i]=map[i][j];
}
}
memset(dp,0x7f,sizeof(dp));
double ans=dp[0][0];
for(int i=1;i<=n;i++){
dp[1<<i-1][1]=map[0][i];
}
for(int i=0;i< (1<<n);i++){
for(int j=1;j<=n;j++){
if( ( (1<< (j-1)) & i )== 0 ) continue;
for(int k=1;k<=n;k++){
if(j==k) continue;
if( (i & (1 << k-1) ) ==0) continue;
dp[i][j]=min(dp[i][j],dp[i ^ (1<< (j-1) ) ][k]+map[j][k]);
}
}
}
for(int i=1;i<=n;i++)
ans=min(ans,dp[(1<<n)-1][i]);
printf("%.2lf",ans);
return 0;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...