旅游

【题目链接】旅游

【题目类型】DP

&题解：

紫书P269 代码很简单，但思路很难。很难能想到要把一个圈分成2条线段，很难想到d(i,j)表示的是已经走过max(i,j)还需要的距离值，当然设d为还需要的距离值，这很常见。

还有也很难想到下一步只能走到i+1。

【时间复杂度】O(n^2)

&代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;

#define cle(a,val) memset(a,(val),sizeof(a))

#define SI(N) scanf("%d",&(N))

#define SII(N,M) scanf("%d %d",&(N),&(M))

#define SIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))

#define rep(i,b) for(int i=0;i<(b);i++)

#define rez(i,a,b) for(int i=(a);i<=(b);i++)

#define red(i,a,b) for(int i=(a);i>=(b);i--)

const ll LINF = 0x3f3f3f3f3f3f3f3f;

#define PU(x) puts(#x);

#define PI(A) cout<<(A)<<endl;

#define DG(x) cout<<#x<<"="<<(x)<<endl;

#define DGG(x,y) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<endl;

#define DGGG(x,y,z) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<" "<<#z<<"="<<(z)<<endl;

#define PIar(a,n) rep(i,n)cout<<a[i]<<" ";cout<<endl;

#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<" ";cout<<endl;}

const double EPS = 1e-9 ;

/*  ////////////////////////   C o d i n g  S p a c e   ////////////////////////  */

const int MAXN = 1000 + 9 ;

struct pnt{

    int x,y;

}p[MAXN];

int n;

double d[MAXN][MAXN];

double dis(int i,int j){

    return hypot(p[i].x-p[j].x,p[i].y-p[j].y);

}

double dp(int i,int j){

    double& ans=d[i][j];

    if (i==n-1) return ans=dis(i,n)+dis(j,n);

    if (ans>0) return ans;

    ans=min(dp(i+1,j)+dis(i,i+1),dp(i+1,i)+dis(j,i+1));

    return ans;

}

void Solve()

{

    while(~SI(n)){

        // dp problem input must start with 1

        rez(i,1,n) SII(p[i].x,p[i].y);

        cle(d,0);

        double ans=dp(1,2)+dis(1,2);

        printf("%.2lf\n", ans);

    }

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("1.in", "r", stdin);

    freopen("1.out","w",stdout);

#endif

//iostream::sync_with_stdio(false);

//cin.tie(0), cout.tie(0);

    // int T;cin>>T;while(T--)

    Solve();

    return 0;

}