POJ 1661 Help Jimmy

아이디어:
1. 각 판자는 좌우 양쪽이 있고 dp[i][0], dp[i][1]는 각각 좌우에서 지면까지의 시간을 기록한다.
2. 아래에서 위로 밀어 계산할 때 윗층의 판자는 반드시 아래의 어느 층의 판자 위에 떨어지거나 바닥에 떨어진다.
 
요약:
1. 각 판자의 dp[i][0/1]를 계산하려면 이 판자의 직접적인 선구자만 고려하면 된다
2. 동규사상이 뚜렷하지 않다
3. 코드에서 두 판의 상대적인 위치에 대한 판단의 정수
4. 바닥과 초기 상태를 하나의 판자로 추상
 
코드:

#include <iostream>
#include <algorithm>
using namespace std;

class board {
public:
	int x1, x2, h;
	board(int _x1, int _x2, int _h):x1(_x1), x2(_x2), h(_h){}
	board() {
		board(-1,-1,-1);
	}
	bool operator <(const board & other) const {
		return this->h < other.h;
	}
};

const int INF = 0X3F3F3F3F;
const int MAXN = 1010;
int t, N, X, Y, H, MAX;
board boards[MAXN];
int dp[MAXN][2];

int mainFunc() {
	
	for(int i = 0; i <= N+1; i ++) {
		for(int j = i-1; j >= 0; j --) {
			if(boards[i].x1 >= boards[j].x1 && boards[i].x1 <= boards[j].x2) { // i          j  
				int h = boards[i].h - boards[j].h;
				if(h > MAX) dp[i][0] = INF;
				else if (j == 0) dp[i][0] = h;
				else 
					dp[i][0] = min(dp[j][0]+boards[i].x1-boards[j].x1, dp[j][1]+boards[j].x2-boards[i].x1) + h;
				break;
			}
		}
		for(int j = i-1; j >= 0; j --) {
			if(boards[i].x2 >= boards[j].x1 && boards[i].x2 <= boards[j].x2) { // i　       　j  
				int h = boards[i].h - boards[j].h;
				if(h > MAX) dp[i][1] = INF;
				else if(j == 0) dp[i][1] = h;
				else
					dp[i][1] = min(dp[j][0]+boards[i].x2-boards[j].x1, dp[j][1]+boards[j].x2-boards[i].x2) + h;
				break;
			}
		}
	}
	return dp[N+1][1];
}

int main() {
	freopen("E:\\Copy\\ACM\\poj\\1661\\in.txt", "r", stdin);
	cin >> t;
	while(t-- >= 1) {
		cin >> N >> X >> H >> MAX;
		for(int i = 0; i < N; i ++) {
			cin >> boards[i].x1 >> boards[i].x2 >> boards[i].h;
		}
		boards[N].x1 = -20010, boards[N].x2 = 20010, boards[N].h = 0;
		boards[N+1].x1 = X, boards[N+1].x2 = X, boards[N+1].h = H;
		sort(boards, boards+N+2);
		// mainFunction
		cout << mainFunc() << endl;
	}
	return 0;
}

　　
업데이트 2014년 3월 16일 10:36:58
1. 직접 전구는 미리 처리할 수 있다