池塘中有n片荷叶恰好围成了一个凸多边形，有一只小青蛙恰好站在1号荷叶上，小青蛙想通过最短的路程遍历所有的荷叶（经过一个荷叶一次且仅一次），小青蛙可以从一片荷叶上跳到另外任意一片荷叶上。
输入数据(frog.in)
第一行为整数n，荷叶的数量。
接下来n行，每行两个实数，为n个多边形的顶点坐标，按照顺时针方向给出。保证不会爆double。
输出数据(frog.out)：
遍历所有荷叶最短路程，请保留3位小数。
数据范围：n <= 720.
这道题一开始可能会想到是区间DP，用dp[i][j]表示走过i～j所有荷叶的最短距离，之后就不会转移了。
想一下问题出现的原因，首先我并不知道青蛙下一步会向哪跳，他有可能直接跳出这个区间，这样就不能很好的转移了。
但是问题恰恰在于考虑的东西太多了。我们不应该直接从一个大区间去考虑一个小区间。首先考虑一个结论：青蛙走过的路线一定不会相交，如果有相交，那么我们就可以把这两条相交的路径变为选取更相近的两条道路，这样肯定是比原来更短的。
于是我们就能推出，青蛙在一个点必然跳往下一个点，或者是末尾的一个点。（因为点都是沿着顺时针方向给出的）
那么我么就有了想法了，用dp[i][j][0/1]表示跳过i～j荷叶的最小距离，其中0/1表示从i/j开始跳，那么就有如下的转移方程：
dp[i][j][0] = min(dp[i+1][j][0] + dis[i][i+1],dp[i+1][j][1] + dis[i][j]);
dp[i][j][1] = min(dp[i][j-1][0] + dis[i][j],dp[i][j-1][1] + dis[j-1][j]);
最后结果即为dp[1][n][0](因为要求从1开始跳)
看一下代码。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<set> #include<queue> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 10005; const ll INF = 1000000009; const int mod = 9397; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } struct point { double x,y; }p[1005]; double calc(int a,int b) { return sqrt((p[a].x - p[b].x) * (p[a].x - p[b].x) + (p[a].y - p[b].y) * (p[a].y - p[b].y)); } double dis[1005][1005],dp[1005][1005][2]; int n; int main() { n = read(); rep(i,1,n) scanf("%lf%lf",&p[i].x,&p[i].y); rep(i,1,n) rep(j,i+1,n) dis[i][j] = dis[j][i] = calc(i,j); rep(i,1,n-1) dp[i][i+1][0] = dp[i][i+1][1] = dis[i][i+1]; rep(L,2,n-1) { rep(i,1,n-L) { int j = i + L; dp[i][j][0] = min(dp[i+1][j][0] + dis[i][i+1],dp[i+1][j][1] + dis[i][j]); dp[i][j][1] = min(dp[i][j-1][0] + dis[i][j],dp[i][j-1][1] + dis[j-1][j]); } } printf("%.3lf ",dp[1][n][0]); return 0; }