P1433 吃奶酪
程序员文章站
2024-01-11 15:28:34
...
这道题大佬貌似都用的状压dp,可惜我不会…还没系统学习dp,只会一点皮毛,虽然不会状压dp,但我会暴搜,暴搜的思路就很简单了,其实就是一个全排列的问题,找出排列路径最短的那一个就是答案,现在的数据好像被加强了,最后一个点TL,dfs+剪枝只有90分,最后一个点我日后学完状压dp再用状压dp写一份,下面是90分代码~(大佬请无视)
#include <iostream>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define Max 1001
float dis[Max][Max]; //从i点到 j点的距离
float nx[Max],ny[Max];
bool flag[Max];
int n;
void dfs(int level,float &res,int now,float length);
int main()
{
ios::sync_with_stdio(false);
cin>>n;
memset(dis,0, sizeof(dis));
memset(flag,false, sizeof(flag));
nx[0]=ny[0]=0;
float res=999999;
for(int i=1;i<=n;i++)
{
cin>>nx[i]>>ny[i]; //输入第 i个点的横纵坐标
}
for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++)
{
dis[i][j]=sqrt(pow(nx[i]-nx[j],2)+pow(ny[i]-ny[j],2));//第i个点和j个点之间的距离
}
}
dfs(0,res,0,0);
cout<<setiosflags(ios::fixed)<<setprecision(2)<<res<<endl;
return 0;
}
void dfs(int level,float &res,int now,float length)
{
if(level==n) //吃完了 n 个奶酪
{
res=min(res,length);
return ;
}
else
{
for(int i=1;i<=n;i++)
{
if(!flag[i])
{
flag[i]=true;
length=length+dis[now][i];
if(length<res) //剪枝
{
dfs(level+1,res,i,length);
}
//还原现场
length-=dis[now][i];
flag[i]=false;
}
}
}
}