定义状态dp[i][j]表示一个人到i,一个人到j,保证i>j
然后倒着推
#include<bits/stdc++.h> using namespace std; const int maxn = 1e3+10; struct node { int x,y; }point[maxn]; double dis(int a,int b) { return sqrt(pow((point[a].x-point[b].x),2)+pow(point[a].y-point[b].y,2)); } double dp[maxn][maxn]; int n; int main() { freopen("in.txt","r",stdin); while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) { scanf("%d%d",&point[i].x,&point[i].y); } memset(dp,0x43,sizeof(dp)); for(int i=n-1;i>1;i--) for(int j=1;j<i;j++) { if(i==n-1) dp[i][j]=dis(n-1,n)+dis(j,n); else dp[i][j]=min(dp[i+1][j]+dis(i,i+1),dp[i+1][i]+dis(j,i+1)); } printf("%.2f\n",dp[2][1]+dis(1,2)); } return 0; }View Code