动态规划 Help Jimmy

POJ 1661

#include <iostream>
#include <algorithm>
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.

当递归算出一个板到地面的距离，用两个数组分别记录左右的结果，下次程序再到这个板时，如果数组已有结果了,就不用再递归去求了