POJ1088 (滑雪)

试了一下深搜每个节点结果TLE了

突然发现是个很明显的DP

从最小的节点开始，更新它四周的节点，如果存在比它高度高的节点，高的节点步数 + 1，因为节点的更新状态肯定是比它高度低那获取的，因此更新时四周比它低的节点已经确定了是最大步数了

// #include<iostream>//POJ 1088滑雪
// #include<cstdio>//深搜试每条路径
// #include<cstring>
// #include<algorithm>
// using namespace std;
// const int maxn = 100 + 15;//地图
// bool vis[maxn][maxn];//判断每个节点是否访问过
// int Map[maxn][maxn];//地图
// int maxLen = 0;//最长路径
// int arrx[] = {1,-1,0,0};
// int arry[] = {0,0,1,-1};
// int R,C;//R代表行数,C代表列数
// void dfs(int x,int y,int len)//从 pos(x,y)坐标开始搜索,len为当前步数
// {
//     maxLen = max(len,maxLen);
//     vis[x][y] = true;//表示坐标已访问过
//     int newx,newy;//新坐标的x,y位置
//     for(int i=0;i!=4;++i)
//     {
//         newx = x + arrx[i];
//         newy = y + arry[i];//新位置
//         if(vis[newx][newy])
//             continue;
//         if(newx<0||newx>=R||newy<0||newy>=C)
//             continue;//防止越界
//         if(Map[newx][newy] < Map[x][y])
//             dfs(newx,newy,len+1);
//         vis[newx][newy] = false;//回溯
//     }
// }
// int main()
// {
//     while(cin>>R>>C)
//     {
//         for(int i=0;i!=R;++i)
//         {
//             for(int j=0;j!=C;++j)
//                 cin>>Map[i][j];//输入地图
//         }
//         for(int i=0;i!=R;++i)
//         {
//             for(int j=0;j!=C;++j)
//             {//从每个点开始尝试
//                 memset(vis,false,sizeof(vis));//重置访问地图
//                 dfs(i,j,1);
//             }
//         }
//         cout<<maxLen<<endl;
//     }
// }
////////////////动规(动态规划)
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;//经典DP
int R,C;//R代表行,C代表列
const int maxn = 100 + 15;
int Map[maxn][maxn];//地图(储存每个点的值)
int cnt[maxn][maxn];
typedef struct
{
    int x,y;//x代表行,y代表列
    int h;//高度
}node;//每个节点代表位置
vector<node> v;
bool cmp(const node& n1,const node& n2)
{
    return n1.h < n2.h;
}
int arrx[] = {1,-1,0,0};
int arry[] = {0,0,1,-1};
int main()//我为人人DP
{
    while(cin>>R>>C)
    {
        node tmp;
        for(int i=0;i!=R;++i)
        {
            for(int j=0;j!=C;++j)
            {
                cnt[i][j] = 1;//初始化步数为1
                tmp.x = i;
                tmp.y = j;
                cin>>tmp.h;
                Map[i][j] = tmp.h;
                v.push_back(tmp);
            }
        }
        //从小到大排序(h)
        sort(v.begin(),v.end(),cmp);
        for(int i=0;i!=R*C;++i)//对于每个节点
        {
            for(int j=0;j!=4;++j)
            {
                int newx = v[i].x + arrx[j];
                int newy = v[i].y + arry[j];
                if(newx<0||newx>=R||newy<0||newy>=C)
                    continue;//防止越界
                if(Map[newx][newy] > v[i].h)
                    cnt[newx][newy] = max(cnt[newx][newy],cnt[v[i].x][v[i].y]+1);
            }
        }
        int maxlen = 0; 
        for(int i=0;i!=R;++i)
        {
            for(int j=0;j!=C;++j)
                maxlen = max(maxlen,cnt[i][j]);
        }
        cout<<maxlen<<endl;
    }
}