吃奶酪
题目描述
房间里放着 $n$ 块奶酪。一只小老鼠要把它们都吃掉,问至少要跑多少距离?老鼠一开始在 $(0,0)$ 点处。
输入格式
第一行有一个整数,表示奶酪的数量 $n$。
第 $2$ 到第 $(n + 1)$ 行,每行两个实数,第 $(i + 1)$ 行的实数分别表示第 $i$ 块奶酪的横纵坐标 $x_i, y_i$。
输出格式
输出一行一个实数,表示要跑的最少距离,保留 $2$ 位小数。
样例 #1
样例输入 #1
4
1 1
1 -1
-1 1
-1 -1
样例输出 #1
7.41
提示
数据规模与约定
对于全部的测试点,保证 $1\leq n\leq 15$,$|x_i|, |y_i| \leq 200$,小数点后最多有 $3$ 位数字。
提示
对于两个点 $(x_1,y_1)$,$(x_2, y_2)$,两点之间的距离公式为 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$。
$2022.7.13$:新增加一组 $\text{Hack}$ 数据。
尝试带记忆化搜索的类bfs,开O2优化能过
(但是如果不带记忆化搜索过不了,因为不满足bfs使用条件,加入队列次序不满足拓扑序,类比求最短路)
切记状态要记录齐,必须记录当前位置和已经走过的位置,不能忽略任何一个,否则就是逻辑漏洞
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
#define speed_up ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
unordered_map<int,double> dist;
pdd a[21];
int n;
int spc(int x,int seq){//手写哈希
return x+(seq+1)*1e6;
}
double get_d(pdd a,pdd b){
double dx=a.first-b.first;
double dy=a.second-b.second;
return sqrt(dx*dx+dy*dy);
}
void bfs(){
dist[spc((1<<n)-1,20)]=0;//设置一个不会冲突的20作为(0,0)点
queue<pii> q;
q.push({(1<<n)-1,20});
while(!q.empty()){
auto t=q.front();
q.pop();
int x=t.first;
pdd old_pd=a[t.second];
for(int i=0;i<n;i++){
if(x>>i&1){
int nx=x-(1<<i);
double nd= get_d(old_pd,a[i]);
if(dist.count(spc(nx,i))==0 ||dist[spc(nx,i)]>dist[spc(x,t.second)]+nd){
dist[spc(nx,i)]=dist[spc(x,t.second)]+nd;
q.push({nx,i});
}
}
}
}
}
int main(){
cin>>n;
a[20]={0,0};
for(int i=0;i<n;i++)cin>>a[i].first>>a[i].second;
bfs();
double ans=1e19;
for(int i=0;i<n;i++)ans=min(ans,dist[spc(0,i)]);
printf("%.2lf",ans);
return 0;
}
状压DP
不得不说状压DP细节真的多,这么简单调半天哈哈我真菜
一定记得初始化!!!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
#define speed_up ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
pdd cheese[17];
int n;
const int N=1<<16;
double f[N][17];
double get_d(pdd a,pdd b){
double dx=a.first-b.first;
double dy=a.second-b.second;
return sqrt(dx*dx+dy*dy);
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<1<<n;j++)f[j][i]=1e9;
}
for(int i=0;i<n;i++){
cin>>cheese[i].first>>cheese[i].second;
f[1<<i][i]= get_d({0,0},cheese[i]);
}
for(int i=0;i<1<<n;i++){
for(int j=0;j<n;j++){
if(!(i>>j&1))continue;
for(int k=0;k<n;k++){
if(i>>k&1){
f[i][j]=min(f[i-(1<<j)][k]+ get_d(cheese[j],cheese[k]),f[i][j]);
}
}
}
}
double ans=1e9;
for(int i=0;i<n;i++){
ans=min(ans,f[(1<<n)-1][i]);
}
printf("%.2lf",ans);
return 0;
}
单纯dfs,能AC一半
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
#define speed_up ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
const int N=17;
pdd cheese[N];
int n;
double get_d(pdd a,pdd b){
double dx=a.first-b.first;
double dy=a.second-b.second;
return sqrt(dx*dx+dy*dy);
}
double dfs(int state,int pos){
if(state==(1<<pos))return get_d({0,0},cheese[pos]);
double ans=1e9;
if((state>>pos&1)==0)return ans;//容易忽略!!!!!!!!!!!
for(int i=0;i<n;i++){
if(state>>i&1){
ans=min(ans, get_d(cheese[i],cheese[pos])+dfs(state-(1<<pos),i));
}
}
return ans;
}
int main(){
cin>>n;
for(int i=0;i<n;i++)cin>>cheese[i].first>>cheese[i].second;
double ans=1e9;
for(int i=0;i<n;i++){
ans=min(ans,dfs((1<<n)-1,i));
}
printf("%.2lf",ans);
return 0;
}
带记忆化搜索dfs,AC
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
#define speed_up ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
const int N=17;
pdd cheese[N];
int n;
double dist[1<<N][N];
double get_d(pdd a,pdd b){
double dx=a.first-b.first;
double dy=a.second-b.second;
return sqrt(dx*dx+dy*dy);
}
double dfs(int state,int pos){
if(dist[state][pos]!=-1)return dist[state][pos];
if(state==(1<<pos))return dist[state][pos]=get_d({0,0},cheese[pos]);
double ans=1e9;
if((state>>pos&1)==0)return dist[state][pos]=ans;
for(int i=0;i<n;i++){
if(state>>i&1){
ans=min(ans, get_d(cheese[i],cheese[pos])+dfs(state-(1<<pos),i));
}
}
return dist[state][pos]=ans;
}
int main(){
cin>>n;
for(int i=0;i<1<<n;i++){
for(int j=0;j<n;j++)dist[i][j]=-1;
}
for(int i=0;i<n;i++)cin>>cheese[i].first>>cheese[i].second;
double ans=1e9;
for(int i=0;i<n;i++){
ans=min(ans,dfs((1<<n)-1,i));
}
printf("%.2lf",ans);
return 0;
}
另一种dfs写法,有启发性
double dfs(int state,int pos){
if(dist[state][pos]!=-1)return dist[state][pos];
if(state==(1<<pos))return dist[state][pos]=get_d({0,0},cheese[pos]);
double ans=1e9;
//if((state>>pos&1)==0)return dist[state][pos]=ans;//不再需要特判,因为不可能发生
for(int i=0;i<n;i++){
if(state>>i&1){
if(i!=pos)ans=min(ans, get_d(cheese[i],cheese[pos])+dfs(state-(1<<pos),i));
}(保证i!=pos可以保证state的第pos位一定不为0)
}
return dist[state][pos]=ans;
}