听说你会打地鼠（动态规划dp）

时间：2021-06-11 08:34:37

题目来源：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

相关文章