uva 10154

dp  记忆化搜索 做的时候像dfs 

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

using namespace std;

struct tur

{

    int x,y,s;

} tur[6000];

int d[6000] = {},n;

int flag[6000] = {};

int _max;

int dp(int i)

{

    int& ans = d[i];

    if(d[i])

        return ans;

    ans = 1;

    for(int j = 1; j < n; j++)

    {

        if(tur[j].x < tur[i].s && !flag[j])

        {

            flag[j] = 1;

            ans = max(ans, dp(j)+1);

            flag[j] = 0;

        }

    }

    return ans;

}

int main()

{

    n = 1;

    tur[0].s = 0x7fffffff;

    while(scanf("%d%d",&tur[n].x,&tur[n].y) == 2)

    {

        tur[n].s = tur[n].y-tur[n].x;

        n++;

    }

    _max = 0;

    for(int i = 1; i < n; i++)

    {

        //memset(d, 0, sizeof(d));

        flag[i] = 1;

        _max = max(_max, dp(i));

        flag[i] = 0;

    }

    printf("%d\n",_max);

    return 0;

}