欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

P1433 吃奶酪

程序员文章站 2024-01-11 15:28:34
...

P1433 吃奶酪

这道题大佬貌似都用的状压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;

                }
            }
        }

    }
相关标签: DFS