poj 2253——Frogger

这个题一开始不知道咋做，但是大致有点意思。后来还是借鉴了题解发现可以用dijkstra，不太理解。但是在最后自己推的时候突然理解了。

dijkstra应该也算是动态规划。我们用dis[i]数组作为青蛙跳到第i个石头时途经的最大跳跃距离。借鉴dijkstra的思路，先找最小的dis[i].然后i作为中间点修改dis[j]，

1<=j<=n;并且U[i]==0;那么对于修改的时候对于点j如果dis[j]>max(dis[i],arcs[i][j]),那么肯定有修改的必要，新的dis[i]=max(dis[i],arcs[i][j])。至于为什么可以这样呢，其实是和dijkstra的证明类似的，但是这里有一个简单的思路。因为我们一开始对于每个点就有最初的dis[j]，当我们可以借助中间点逐渐优化的时候，那么dis[j]肯定是越来越优化的，直到结束。其实这样想有点像floyd。动态规划真的是神奇啊！

Ps：今天历经坎坷，终于组队了。虽然水平都不高，但是距离区域赛还有6个月！we can make it!

 #include <iostream>

 #include <cstring>

 #include <string>

 #include <map>

 #include <set>

 #include <algorithm>

 #include <fstream>

 #include <cstdio>

 #include <cmath>

 #include <stack>

 #include <queue>

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 using namespace std;

 const double Pi=3.14159265358979323846;

 typedef long long ll;

 const int MAXN=+;

 const int dx[]={,,,-};

 const int dy[]={,-,,};

 const int INF = 0x3f3f3f3f;

 const int NINF = 0xc0c0c0c0;

 const ll mod=1e9+;

 struct graph

 {

     double weight;

     double arcs[MAXN][MAXN];

 }G;

 struct node{

     int a,b;

 }p[MAXN];

 double dis[MAXN];

 //v是起点，n是一共的点的个数

 //dis[i]记录的是从七点到i，所有路径中的最小单步值

 void dijkstra(int v,int n)

 {

     int U[MAXN];

     for(int i=;i<=n;i++) U[i]=;

     for(int i=;i<=n;i++) dis[i]=INF; dis[v]=;

     for(int i=;i<=n;i++)

     {

         double minn=INF;int k=-;

         /*for(int j=1;j<=n;j++)

         {

             cout <<dis[j]<<" ";

         }

         cout <<endl<<"**********"<<endl;*/

         for(int i=;i<=n;i++)

         {

             if(minn>dis[i]&&U[i]==)

             {

                 minn=dis[i];

                 k=i;

             }

         }

         U[k]=;

         for(int i=;i<=n;i++)

         {

             if(U[i]==&&dis[i]>max(G.arcs[i][k],dis[k]))

             {

                 dis[i]=max(G.arcs[i][k],dis[k]);

             }

         }

     }

 }

 int main()

 {

     int n;int cnt=;

     while(scanf("%d",&n)&&n)

     {

         for(int i=;i<=n;i++)

         {

             scanf("%d%d",&p[i].a,&p[i].b);

         }

         for(int i=;i<n;i++)

         {

             for(int j=i+;j<=n;j++)

             {

                 G.arcs[i][j]=sqrt((p[i].a-p[j].a)*(p[i].a-p[j].a)+(p[i].b-p[j].b)*(p[i].b-p[j].b));

                 G.arcs[j][i]=G.arcs[i][j];

             }

         }

         dijkstra(,n);

         printf("Scenario #%d\n",cnt++);

         printf("Frog Distance = %.3f\n\n",dis[]);

     }

     return ;

 }

巴特西

poj 2253——Frogger

最新文章

热门文章