poj 2253（区间DP）

男娘i 2022-06-04 03:05 216阅读 0赞

[原题][Link 1]

思路：求所有路径中最大跳跃距离的最小值， 很诡异的是输出答案如果用G++，.3lf%格式会出错，c++可以过

#include<cstdio>
    #include<cmath>
    #include<vector>
    #include<iostream>
    #include<stack>
    #include<cstring>
    using namespace std;
    const double INF=0x3f3f3f3f;
    const int maxn=2e2+10;
    double mp[maxn][maxn], dis[maxn][maxn], cor[maxn][maxn];
    int n;
    int main(){
        int cas=0;
        while(~scanf("%d", &n) && n)
        {
            for(int i=1; i<=n; i++)
            {
                scanf("%lf%lf", &cor[i][0], &cor[i][1]);
                //cout<<cor[i][0]<<" "<<cor[i][1]<<endl;
            }
    
            for(int i=1; i<=n; i++)
            {
                for(int j=1; j<=n; j++)
                {
                    double x2, y2;
                    x2=(cor[i][0]-cor[j][0])*(cor[i][0]-cor[j][0]);
                    y2=(cor[i][1]-cor[j][1])*(cor[i][1]-cor[j][1]);
                    dis[i][j]=mp[i][j]=sqrt(x2 + y2);
                   //cout<<mp[i][j]<<" ";
    
    
                }
               //cout<<endl;
            }
    
            for(int k=1; k<=n; k++)
                for(int i=1; i<=n; i++)
                    for(int j=1; j<=n; j++)
                        dis[i][j]=min(dis[i][j], max(dis[i][k], dis[k][j]));
    
            printf("Scenario #%d\n", ++cas);
            printf("Frog Distance = %.3lf\n\n", dis[1][2]);
        }
        return 0;
    }

[Link 1]: http://poj.org/problem?id=2253

发表评论取消回复

表情：

评论列表（有 0 条评论，216人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 3280 Cheapest Palindrome（区间DP）

嗯... 题目链接：http://poj.org/problem?id=3280 这道题首先要清楚：对于构成一个回文串，删去一个字符和加上一个字符是等效的，所以

谁借莪１个温暖的怀抱￠/ 2023年06月04日 13:57/ 0 赞/ 104 阅读

相关 poj（3280）Cheapest Palindrome（区间dp）

题目链接：[http://poj.org/problem?id=3280][http_poj.org_problem_id_3280] 题意：给出一个由m

阳光穿透心脏的1/2处/ 2022年08月26日 15:36/ 0 赞/ 119 阅读

相关 POJ 2955-Brackets（括号匹配-区间DP）

Brackets <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

短命女/ 2022年08月22日 12:30/ 0 赞/ 160 阅读

相关 poj 1141 （区间dp记录路径问题）

题意：括号匹配问题。问需要插入多少个括号是的所有的括号都正好可以匹配。输出其中长度最短的一个。分析：dp\[i\]\[j\] 表示的是在区间(i,j)之间添加的最少的括号数

忘是亡心i/ 2022年08月18日 11:56/ 0 赞/ 133 阅读

相关 POJ 2955 区间dp

题意：求括号匹配的最大长度思路：简单区间dp，令dp\[i\]\[j\] 为区间（i,j）之间的最大匹配长度。这样dp\[i\]\[j\] = max( dp\[i

Love The Way You Lie/ 2022年08月18日 11:55/ 0 赞/ 199 阅读

相关 POJ 2253 Frogger floyd变形

滴，集训第二十五天打卡。最近又好热好热了呀... POJ 2253 Frogger Freddy Frog is sitting on a stone in the m

曾经终败给现在/ 2022年06月10日 05:55/ 0 赞/ 146 阅读

相关 poj 2253（区间DP）

[原题][Link 1] 思路：求所有路径中最大跳跃距离的最小值，很诡异的是输出答案如果用G++，.3lf%格式会出错，c++可以过 include<cstdio

男娘i/ 2022年06月04日 03:05/ 0 赞/ 217 阅读

相关 poj-2253-Frogger

Frogger <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

ゝ一世哀愁。/ 2022年05月28日 12:07/ 0 赞/ 114 阅读

相关 POJ1179 Polygon（区间dp）

题意：多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“+”或“\”。所有边依次用整数从1到n编号，游戏第1

蔚落/ 2021年11月29日 14:56/ 0 赞/ 315 阅读