동적 계획 Help Jimmy

2750 단어
POJ 1661
 
#include #include using namespace std; const int NAN = 200000001; int t; int N; int X; int Y; int MAX; class Plat { public: int x1; int x2; int h; Plat(int x1 = 0, int x2 = 0, int h = 0) : x1(x1),x2(x2),h(h) { } void reset() { x1 = 0; x2 = 0; h = 0; } void display() { cout << x1 << ","<< x2 << ","<< h << endl; } }; Plat p[1001]; int L[1001]; int R[1001]; void reset(int N) { for(int i = 0; i <=N; i++) { L[i] = 0; R[i] = 0; p[i].reset(); } } void print(int N) { for(int i = 0; i <= N; i++) { p[i].display(); } } bool isReachable(int i) { return (p[i].h <= MAX); }/* * find the lower platform which the end point can fall down * direct: * 1 - left * 0 - right * return -1 if no more plat, then, shall check reachable directly */int findNextPlat(int current, int direct) { int x = (direct ? p[current].x1 : p[current].x2); int h = p[current].h; for(int i = current + 1; i <= N; i++) { int x1 = p[i].x1; int x2 = p[i].x2; if ((x1 <= x) && (x <= x2)) { if ( h - p[i].h <= MAX) { return i; } else { return -1; } } } return -1; }/* * find the shortest path from current to ground, in direction left(1) or right(0) */int sp(int current, int direct) { int x = (direct ? p[current].x1 : p[current].x2); int h = p[current].h; int next = findNextPlat(current, direct); if (next > -1) { if (L[next] == 0) { L[next] = sp(next, 1); } if (R[next] == 0) { R[next] = sp(next, 0); } int left = L[next] + x - p[next].x1 + (h - p[next].h); int right = R[next] + p[next].x2 - x + (h - p[next].h); return min (left, right); } else { if (isReachable(current)) {//direct ? (L[current] = h) : (R[current] = h); return h; } else {//direct ? (L[current] = NAN) : (R[current] = NAN); return NAN; } } } class Comp { public: bool operator()(Plat me, Plat that) { return me.h > that.h; } } c; int main() { cin >> t; for (int i = 0; i < t; i++) { cin >> N >> X >> Y >> MAX; p[0].x1 = X; p[0].x2 = X; p[0].h = Y; for(int j = 1; j <= N; j++) { cin >> p[j].x1 >> p[j].x2 >> p[j].h; } sort(p, p+N+1, c);//cout << "the platforms are "<< endl;//print(N);//cout << endl; cout << min(sp(0, 1), sp(0, 0)) << endl;/* for(int i= 0; i <= N; i++) { cout << L[i] << ""; } cout << endl; for(int i= 0; i <= N; i++) { cout << R[i] << ""; } cout << endl; */reset(N); } }
 
데이터:http://iskren.info/info-arh/CEOI/2000/tests/falling/
 
체득:xuchang 인용:사실 DP의 방향과 상관없는 관건은 기억화 DP를 사용하는 것이다.
              ，              ，          ，         ,

내 도메인 이름으로 메일을 보내고 싶은데 어떡하지?
[Leetcode] 70. 계단 오 르 기

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage