[DP|폭력] POJ-1661 Help Jimmy

Help Jimmy Time Limit: 1000MS Memory Limit: 10000K
Description "Help Jimmy"는 다음 그림과 같은 장면에서 완성된 게임입니다.
장면에는 여러 개의 길이와 높이가 각각 다른 플랫폼이 포함되어 있다.지면은 가장 낮은 플랫폼으로 높이는 0이고 길이는 무한하다.
Jimmy 쥐는 시시각각 0이 모든 플랫폼보다 높은 곳에서 떨어지기 시작하는데, 그것의 떨어지는 속도는 시종 1미터/초이다.Jimmy가 어떤 플랫폼에 떨어졌을 때, 게임자들은 그것을 왼쪽으로 뛸지 오른쪽으로 뛸지 선택했고, 그것이 달리는 속도도 1미터/초였다.Jimmy가 플랫폼의 가장자리까지 달렸을 때, 계속 떨어지기 시작했다.지미는 매번 떨어지는 높이가 맥스미터를 넘으면 안 된다. 그렇지 않으면 넘어져 죽고 게임도 끝난다.
Jimmy가 바닥에 닿을 때 가능한 가장 빠른 시간을 계산하는 프로그램을 설계합니다.
Input 첫 번째 행은 테스트 데이터의 그룹 수 t(0 <=t <=20)입니다.각 테스트 데이터의 첫 줄은 네 개의 정수 N, X, Y, MAX로 공백으로 구분된다.N은 플랫폼의 수(지면 포함)이며, X와 Y는 지미가 떨어지기 시작한 위치의 가로세로 좌표이며, 맥스는 한 번에 떨어지는 최대 높이다.다음 N줄은 세 개의 정수, X1[i], X2[i]와 H[i]를 포함하는 플랫폼을 한 줄씩 설명한다.H[i]는 플랫폼의 높이를 나타내고X1[i]와 X2[i]는 플랫폼의 좌우 단점의 가로 좌표를 나타낸다.1 <= N <= 1000,-20000 <= X, X1[i], X2[i] <= 20000,0 < H[i] < Y <= 20000(i = 1..N).모든 좌표의 단위는 미터다.
Jimmy의 크기와 플랫폼의 두께는 무시됩니다.만약 Jimmy가 마침 어느 플랫폼의 가장자리에 떨어진다면, 플랫폼에 떨어진 것으로 간주된다.모든 플랫폼이 겹치거나 연결되지 않습니다.테스트 데이터는 문제가 반드시 해결될 것을 보증한다.
Output은 입력한 각 그룹의 테스트 데이터를 정수로 출력하고 Jimmy가 바닥에 닿을 때 가능한 가장 빠른 시간을 출력합니다.
Sample Input
1 3 8 17 20 0 10 8 0 10 13 4 14 3
Sample Output
23
Source POJ Monthly–2004.05.15 CEOI 2000
사고방식: 사고방식이 너무 폭력적이어서 생각을 못했어...참조: ACVon은 먼저 dp[i][2]는 상태를 나타내는데 플랫폼 i 양단점의 최단로에 도달한다는 뜻이다.나머지는 매거다...지면은 플랫폼으로 삼아 연산에 참여하지 않기 때문에 마지막으로 지면으로 뛰어내리는 판단을 해야 한다.코드는 다음과 같습니다.

/*
 * ID: j.sure.1
 * PROG:
 * LANG: C++
 */
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define PB push_back
#define LL long long
using namespace std;
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
/****************************************/
const int N = 1005;
int n, lim, sx, sy;
struct Node {
    int x[2], h;
    bool operator < (const Node &rhs) const {
        return h > rhs.h;
    }
}a[N];
int dp[N][2];

//          
int solve()
{
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = dp[0][1] = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < i; j++) {
            for(int d = 0; d < 2; d++) {
                if(a[i].x[0] <= a[j].x[d] && a[i].x[1] >= a[j].x[d]) {
                    if(a[j].h - a[i].h <= lim) {
                        bool ok = true;
                        for(int k = j+1; k < i; k++) {
                            if(a[k].x[0] <= a[j].x[d] && a[k].x[1] >= a[j].x[d]) {
                                ok = false;
                                break;
                            }
                        }//       
                        if(ok && dp[j][d] != INF) {
                            int tmp = dp[j][d] + a[j].h - a[i].h + abs(a[j].x[d] - a[i].x[0]);
                            dp[i][0] = min(dp[i][0], tmp);
                            tmp = dp[j][d] + a[j].h - a[i].h + abs(a[j].x[d] - a[i].x[1]);
                            dp[i][1] = min(dp[i][1], tmp);
                        }
                    }
                }
            }
        }
    }
    printf("dp[n][0] is %d, dp[n][1] is %d
", dp[n][0], dp[n][1]);
    //dp        
    int ans = INF;
    for(int i = 0; i <= n; i++) {
        if(a[i].h <= lim) {
            for(int d = 0; d < 2; d++) {
                bool ok = true;
                for(int k = i+1; k <= n; k++) {
                    if(a[k].x[0] <= a[i].x[d] && a[k].x[1] >= a[i].x[d]) {
                        ok = false;
                        break;
                    }
                }
                if(ok) {
                    ans = min(ans, dp[i][d] + a[i].h);
                }
            }
        }
    }
    return ans;
}

int main()
{
#ifdef J_Sure
    freopen("000.in", "r", stdin);
    //freopen("999.out", "w", stdout);
#endif
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d%d%d", &n, &sx, &sy, &lim);
        a[0].x[0] = a[0].x[1] = sx;
        a[0].h = sy;
        for(int i = 1; i <= n; i++) {
            scanf("%d%d%d", &a[i].x[0], &a[i].x[1], &a[i].h);
        }
        sort(a, a+n+1);
        int ans = solve();
        printf("%d
", ans);
    }
    return 0;
}