poj 1088 滑雪（贪心算法）

思想： （贪心算法 ，看到题目是中文才做的）

• 先对数组中的数据进行排序，从最小的数据计算 当前的顶点的可以滑行的最大值=max（周围可达的顶点的可以滑行的最大值）+1
• 这样计算最后产生的路径肯定是最大的
• （看discuss中，有动态规划和dfs实现的代码，回头看看）

  #include <iostream>
  #include <algorithm>
  using namespace std;
  #define MAX 10005
  /*488K63MS*/
  typedef struct _point
  {
  int x;
  int y;
  int w;//权重
  }point;int cmp(const void *a,const void *b);
  int main()
  {
  int r,c;
  cin>>r>>c; point p[MAX];
  int a[102][102];
  int index=0;
  for(int i=0;i<r;i++)
  for(int j=0;j<c;j++)
  {
  p[index].x=i;
  p[index].y=j;
  cin>>a[i][j];
  p[index++].w=a[i][j];
  } qsort(p,index,sizeof(p[0]),cmp); //贪心算法
  int b[102][102];
  memset(b,0,sizeof(b)); int result=0;
  for(int i=0;i<index;i++)
  {
  //计算四周的值的大小
  int max=1;
  int x=p[i].x;
  int y=p[i].y;
  int w=p[i].w;
  //up
  if(x>0)
  {
  if(w>a[x-1][y]&&max<=b[x-1][y])
  max=b[x-1][y]+1;
  }
  //down
  if(x<r-1)
  {
  if(w>a[x+1][y]&&max<=b[x+1][y])
  max=b[x+1][y]+1;
  }
  //left
  if(y>0)
  {
  if(w>a[x][y-1]&&max<=b[x][y-1])
  max=b[x][y-1]+1;
  }
  //right
  if(y<r-1)
  {
  if(w>a[x][y+1]&&max<=b[x][y+1])
  max=b[x][y+1]+1;
  }
  b[x][y]=max;
  if(result<max)
  result=max;
  } cout<<result<<endl;
  system("pause");
  return 0;
  }int cmp(const void *a,const void *b)
  {
  return ((*(point *)a).w-(*(point *)b).w);
  }