Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

简单DP水题,一遍过,应该是O(N3)

Posted by KatrineYang at 2017-01-23 04:44:06 on Problem 1556 and last updated at 2017-01-23 04:52:04
#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;

struct pt{
	double x,y;
	pt(){x=y=0;}
	pt(double x,double y):x(x),y(y){}
};

double dis(pt &p1, pt &p2){
	return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}

pt start, end;

int n;
double wall[100][5];
double dist[100][5];

bool ky(pt &p1, pt &p2){
	//p1 is x-smaller than p2
	for(int i = 0; i < n; i++){
		if(wall[i][0] <= p1.x) continue;
		if(wall[i][0] >= p2.x) break;
		double wx = wall[i][0];
		double wy = p1.y + (p2.y-p1.y)/(p2.x-p1.x)*(wx-p1.x);
		if(wy <= wall[i][1] || (wy >= wall[i][2] && wy <= wall[i][3]) || wy >= wall[i][4]) return false;
	}
	return true;
}

int main() {
	start.x = 0, start.y = 5;
	end.x = 10, end.y = 5;
	while(1){
		scanf("%d", &n);
		if(n<0) break;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < 5; j++){
				scanf("%lf", &wall[i][j]);
			}
		}
		if(ky(start, end)){
			printf("10.00\n");
			continue;
		}
		for(int i = 0; i < n; i++){
			for(int j = 1; j < 5; j++){
				pt ep(wall[i][0], wall[i][j]);
				if(ky(start, ep)) dist[i][j] = dis(ep, start);
				else{
					double minDist = 1e10;
					for(int k = 0; k < i; k++){
						for(int l = 1; l < 5; l++){
							pt mp(wall[k][0], wall[k][l]);
							if(ky(mp, ep)){
								double newDist = dis(ep,mp) + dist[k][l];
								if(newDist < minDist) minDist = newDist;
							}
						}
					}
					dist[i][j] = minDist;
				}
			}
		}
		double ans = 1e10;
		for(int k = 0; k < n; k++){
			for(int l = 1; l < 5; l++){
				pt mp(wall[k][0], wall[k][l]);
				if(ky(mp, end)){
					double newAns = dis(mp,end) + dist[k][l];
					if(newAns < ans) ans = newAns;
				}
			}
		}
		printf("%.2lf\n", ans);
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator