两个人同时从最左端出发,不会走相同的点,且出了起点和终点每个点恰好被一个人走一次,求到最右端的最小。
用dp[i][j] 表示快的人走到i 慢的人走到[j]
走到i点的情况:
1. 快的小人走到i,则有dp[i][j]=min(dp[i][j],dp[i-1][j]+dis(i-1,i));
2. 慢的小人走到i,则有dp[i][i-1]=min(dp[i][i-1],dp[i-1][j]+dis(i,j));
最后,必然是快的小人走到终点n,我们还要搜寻慢的小人在那个位置时总的路径最短。
#include <iostream> #include <cstring> #include <cstdio> #include <cmath> #define MAX 110 using namespace std; double dp[MAX][MAX]; int x[MAX],y[MAX]; double dis(int i,int j) { return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); } int main() { int n; while(scanf("%d",&n) != EOF) { for(int i = 1; i <= n; i++) { scanf("%d%d",&x[i],&y[i]); } for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) { dp[i][j] = 1e10; } dp[1][1] = 0; for(int i = 2; i <= n; i++) for(int j = 1; j < i; j++) { dp[i][j] = min(dp[i][j],dp[i-1][j] + dis(i-1,i)); dp[i][i-1] = min(dp[i][i-1],dp[i-1][j] + dis(i,j)); } double temp = 1e10; for(int i = 1;i < n;i++) temp = min(temp , dp[n][i] + dis(i,n)); printf("%.2f ",temp); } return 0; }