题目来源：https://biancheng.love/contest-ng/index.html#/41/problems
G 听说你会打地鼠
时间限制：300ms 内存限制：65536kb
题目描述
打地鼠是个很简单的游戏，不过你知道怎么打地鼠才能最省力吗？
每时刻，都有N只地鼠在pi(xi,yi)位置出现，打掉一只，该时刻其他地鼠会消失。
打掉第一只地鼠不消耗能量，之后每只地鼠消耗的能量约与鼠标移动距离成正比，即cost = dis(pi,pi+1)（平面上两点距离怎么求不多说了）
现在认为打第一只地鼠不消耗能量，那么打完所有地鼠消耗的最小能量是多少？
输入
多组测试数据
每组测试数据第一行两个整数为时长K和每时刻地鼠数量N
接下来N行每行2N个整数表示N只地鼠坐标
N<=100,K<40
输出
对于每组数据，输出一行，为最小消耗,结果保留3位小数
输入样例
2 2
1 1 3 4
2 2 5 3输出样例
1.414
解题思路：
状态转移方程：
dp[k][i]=dp[k-1][j]+cost(p[k][i],p[k-1][j]);
说明：dp[k][j] 表示打第k层第j个的时候所能得到的最小值
给出代码：
#include <bits/stdc++.h>
#define INF 9999999999 using namespace std;
struct Point{
double x;
double y;
}; double cost(Point a,Point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
} Point p[][];
double dp[][];
int k,n,i,j,f;
double ans;
int main()
{
while(~scanf("%d%d",&k,&n))
{
ans=INF;
for(i=;i<k;i++)//k层
{
for(j=;j<n;j++)//n个
{
scanf("%lf%lf",&p[i][j].x,&p[i][j].y);//x表示层数，y表示第几个，因此p[x][y]可以确定所选择的地鼠层数以及在该层的位置
}
}
for(f=;f<k;f++)
{
for(i=;i<n;i++)
{
dp[f][i]=INF;
}
}
// memset(find_min,INF,sizeof(find_min));
for(f=;f<n;f++)
{
dp[][f]=;//第一只不需要消耗能量
}
for(f=;f<k;f++)//第f层
{
for(i=;i<n;i++)
{
for(j=;j<n;j++)
{
if(dp[f][i]>(dp[f-][j]+cost(p[f][i],p[f-][j])))//状态转移方程
dp[f][i]=dp[f-][j]+cost(p[f][i],p[f-][j]);//在第f层最小消耗能量等于在第f-1层打第j个地鼠+两点之间距离
}
}
}
for(i=;i<n;i++)
{
if(ans>dp[k-][i])
ans=dp[k-][i];
}
printf("%.3lf\n",ans);
}
}
推荐博客：http://www.tuicool.com/articles/QV7rQjZ