首页 > 代码库 > POJ 2677 Tour DP
POJ 2677 Tour DP
双调欧几里得问题,复习一下。。
把所有的点按照x排序,设计状态f(i,j)表示走在前面的那个走到了i点,后面那个在j点,所需的最小,那么转移显而易见。
f(i,j) = min(f(i - 1,j) + dist(i,i - 1), f(i,i - 1) + dist(i,j))
直接顺着推过去可能好理解一些。。
当前状态f(i,j) 如果由i走到i + 1,那么就是f(i + 1,j),否则就是f(i + 1,i)..
#include <cstdio>#include <cstring>#include <iostream>#include <map>#include <set>#include <vector>#include <string>#include <queue>#include <deque>#include <bitset>#include <list>#include <cstdlib>#include <climits>#include <cmath>#include <ctime>#include <algorithm>#include <stack>#include <sstream>#include <numeric>#include <fstream>#include <functional>using namespace std;#define MP make_pair#define PB push_backtypedef long long LL;typedef unsigned long long ULL;typedef vector<int> VI;typedef pair<int,int> pii;const int INF = INT_MAX / 3;const double eps = 1e-8;const LL LINF = 1e17;const double DINF = 1e60;const int maxn = 500;struct Point { double x,y; Point(double x = 0,double y = 0): x(x), y(y) {} bool operator < (const Point &p) const { if(fabs(p.x - x) < eps) return y < p.y; return x < p.x; }};double sq(double x) { return x * x; }int n;double f[maxn][maxn];Point p[maxn];double dist[maxn][maxn];int main() { while(scanf("%d",&n) != EOF) { for(int i = 1;i <= n;i++) { scanf("%lf%lf",&p[i].x,&p[i].y); } for(int i = 1;i <= n;i++) { for(int j = 1;j <= n;j++) { f[i][j] = DINF; } } sort(p + 1, p + 1 + n); for(int i = 1;i <= n;i++) { for(int j = 1;j <= n;j++) if(i != j) { dist[i][j] = sqrt(sq(p[i].x - p[j].x) + sq(p[i].y - p[j].y)); } } double ans = DINF; f[1][1] = 0; for(int i = 1;i <= n;i++) { int m = i == 1 ? 1 : i - 1; for(int j = 1;j <= m;j++) { f[i + 1][i] = min(f[i + 1][i], f[i][j] + dist[j][i + 1]); f[i + 1][j] = min(f[i + 1][j], f[i][j] + dist[i][i + 1]); if(i == n) { ans = min(ans, f[i][j] + dist[j][n]); } } } printf("%.2f\n",ans); } return 0;}
POJ 2677 Tour DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。