OpenJudge/Poj 1088 滑雪

1.链接地址：

bailian.openjudge.cn/practice/1088

http://poj.org/problem?id=1088

2.题目：

3.思路：

动态规划，先按照高度降序排序，再依次计算

刚开始想当然，以为从最高高度寻找一个路径一定是最长，所以使用了优先队列+广搜，白白WA了一次

4.代码：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 using namespace std;

 struct PATH

 {

     int x;

     int y;

     int height;

 };

 int cmp(const void* a,const void *b)

 {

     PATH *p1 = (PATH *) a;

     PATH *p2 = (PATH *) b;

     return p2->height - p1->height;

 }

 int main()

 {

     //freopen("C://input.txt","r",stdin);

     int r,c;

     cin >> r >> c;

     int i,j;

     int **arr_height = new int*[r];

     for(i = ; i < r; ++i) arr_height[i] = new int[c];

     int **arr_mark = new int*[r];

     for(i = ; i < r; ++i)

     {

         arr_mark[i] = new int[c];

         memset(arr_mark[i],,sizeof(int) * c);

     }

     PATH *arr_path = new PATH[r * c];

     for(i = ; i < r; ++i)

     {

         for(j = ; j < c; ++j)

         {

             cin >> arr_height[i][j];

             arr_path[i * c + j].x = j;

             arr_path[i * c + j].y = i;

             arr_path[i * c + j].height = arr_height[i][j];

         }

     }

     qsort(arr_path,r * c,sizeof(PATH),cmp);

     int idx_x[] = {-,,,};

     int idx_y[] = {,,,-};

     int res = ;

     for(i = ; i < r * c; ++i)

     {

         //cout << arr_path[i].height << " " << arr_path[i].x << " " << arr_path[i].y << endl;

         int max = ;

         for(j = ; j < ; ++j)

         {

             int temp_x = arr_path[i].x + idx_x[j];

             int temp_y = arr_path[i].y + idx_y[j];

             if(temp_x <  || temp_x >= c || temp_y <  || temp_y >= r) continue;

             if(arr_height[temp_y][temp_x] > arr_height[arr_path[i].y][arr_path[i].x] && max < arr_mark[temp_y][temp_x])

             {

                 max = arr_mark[temp_y][temp_x];

             }

         }

         arr_mark[arr_path[i].y][arr_path[i].x] = max + ;

         if(res < max + ) res = max + ;

     }

     cout << res << endl;

     delete [] arr_path;

     for(i = ; i < r; ++i) delete [] arr_height[i];

     delete [] arr_height;

     for(i = ; i < r; ++i) delete [] arr_mark[i];

     delete [] arr_mark;

     return ;

 }