poj 2253（区间DP）
原题
思路：求所有路径中最大跳跃距离的最小值， 很诡异的是输出答案如果用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;}
Love The Way You Lie
还没有评论，来说两句吧...