其实质是求最长非降子序列（两两相邻），设每个点的状态变量为从比其高度小的点到其最长的滑雪路径的长度，可以先对所有点的高度进行排序，按高度从小到大进行状态转移（其前驱状态为上下左右四个相邻点），求出最大状态变量即可。题目来源：上海市NOI2002选拔赛第一试。

bbb

#1 Accepted 1572ms 108.68 MiB
#2 Accepted 691ms 67.355 MiB
#3 Accepted 962ms 90.551 MiB
#4 Accepted 431ms 35.125 MiB
#5 Accepted 1242ms 101.719 MiB
#6 Accepted 528ms 42.645 MiB
#7 Accepted 481ms 40.414 MiB
#8 Accepted 1047ms 99.492 MiB
#9 Accepted 782ms 69.82 MiB
#10 Accepted 1025ms 111.48 MiB
不谈了 自己用java写了一下 真厉害啊。难道java天生就是慢嘛？？工作了，空的时候用java玩玩

import java.util.Scanner;
public class Main {
public int[][] m = new int[501][501];
public int[][] dp = new int[501][501];
public int[] mx = { 0, 1, 0, 0, -1 };
public int[] my = { 0, 0, 1, -1, 0 };
public int r, c;
public Main() {
int i = 0, j = 0;
Scanner sc = new Scanner(System.in);
r = sc.nextInt();
c = sc.nextInt();
for (i = 1; i <= r; i++)
for (j = 1; j <= c; j++) {
m[i][j] = sc.nextInt();
dp[i][j] = 1;
}
}
public int dpSearch(int x, int y) {
if (dp[x][y] > 1)
return dp[x][y];
int i = 0, j = 0;
boolean flag = false;
for (i = 1; i <= 4; i++) {
int k = x + mx[i];
int v = y + my[i];
if (k >= 1 && k <= r && v >= 1 && v <= c && m[k][v] < m[x][y]) {
dp[x][y] = Math.max(dp[x][y], dpSearch(k, v) + 1);
}
}
return dp[x][y];

}
public static void main(String[] args) {
// TODO Auto-generated method stub
Main dpClass = new Main();
int max = -1;
for (int i = 1; i <= dpClass.r; i++)
for (int j = 1; j <= dpClass.c; j++)
max = Math.max(max, dpClass.dpSearch(i, j));
System.out.println(max);
}

}

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i <= _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i >= _##i; --i)
#define mem(f,x) memset(f,x,sizeof(f))
//========================================================================
int n, m;
int c[505][505];
long st[505][505];
long dfs(int x, int y) {
    if (st[x][y] != -1) return st[x][y];
    long tmp = 0;
    if ((x > 1) && (c[x - 1][y] < c[x][y])) tmp = max(tmp, dfs(x - 1, y));
    if ((y > 1) && (c[x][y - 1] < c[x][y])) tmp = max(tmp, dfs(x, y - 1));
    if ((x < n) && (c[x + 1][y] < c[x][y])) tmp = max(tmp, dfs(x + 1, y));
    if ((y < m) && (c[x][y + 1] < c[x][y])) tmp = max(tmp, dfs(x, y + 1));
    st[x][y] = tmp + 1;
    return st[x][y];
}
int main()
{
    cin >> n >> m;
    FOR(i, 1, n) {
        FOR(j, 1, m) {
            cin >> c[i][j];
        }
    }
    long xmax = -1;
    mem(st, -1);
    FOR(i, 1, n) {
        FOR(j, 1, m) {
            xmax=max(xmax,dfs(i, j));
        }
    }
    cout << xmax << endl;
    return 0;
}

记忆化搜索

#include<cstdio>
#include<algorithm>
using namespace std;
template<class T> inline void read(T &_a){
    bool f=0;int _ch=getchar();_a=0;
    while(_ch<'0' || _ch>'9'){if(_ch=='-')f=1;_ch=getchar();}
    while(_ch>='0' && _ch<='9'){_a=(_a<<1)+(_a<<3)+_ch-'0';_ch=getchar();}
    if(f)_a=-_a;
}

int n,m,mp[502][502],memory[501][501],ans;

int dfs(int x,int y)
{
    if(memory[x][y]) return memory[x][y];
    if(x<n) if(mp[x+1][y]<mp[x][y]) memory[x][y]=max(memory[x][y],dfs(x+1,y)+1);
    if(y<m) if(mp[x][y+1]<mp[x][y]) memory[x][y]=max(memory[x][y],dfs(x,y+1)+1);
    if(x>1) if(mp[x-1][y]<mp[x][y]) memory[x][y]=max(memory[x][y],dfs(x-1,y)+1);
    if(y>1) if(mp[x][y-1]<mp[x][y]) memory[x][y]=max(memory[x][y],dfs(x,y-1)+1);
    if(!memory[x][y]) memory[x][y]=1;
    return memory[x][y];
}

int main()
{
    read(n); read(m);
    for (register int i=1;i<=n;++i)
     for (register int v=1;v<=m;++v)
      read(mp[i][v]);
    for (register int i=1;i<=n;++i)
     for (register int v=1;v<=m;++v)
      ans=max(ans,dfs(i,v));
    printf("%d",ans);
    return 0;
} 

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;

const int maxn=505;

struct node{int val,x,y;};

int xx,yy,ans;
int a[maxn][maxn],dp[maxn][maxn];
int dx[5]={0,1,-1,0,0},dy[5]={0,0,0,1,-1};

priority_queue<node>v;

bool operator < (const node &a,const node &b){return a.val>b.val;}

int read()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();
return x;
}
int main()
{
int fx,fy;
scanf("%d%d",&yy,&xx);
for(int i=1;i<=yy;i++)

for(int j=1;j<=xx;j++)
v.push((node){a[j][i]=read(),j,i});
for(int i=1;i<=yy;i++)
for(int j=1;j<=xx;j++)
dp[j][i]=1;
while(!v.empty())
{
node tmp=v.top();
v.pop();
for(int i=1;i<=4;i++)
{
fx=tmp.x+dx[i];
fy=tmp.y+dy[i];
if(fx<1||fx>xx||fy<1||fy>yy)continue;
if(a[fx][fy]>tmp.val)
dp[fx][fy]=max(dp[fx][fy],dp[tmp.x][tmp.y]+1);
}
}

for(int i=1;i<=yy;i++)
for(int j=1;j<=xx;j++)
ans=max(ans,dp[j][i]);
printf("%d",ans);
return 0;
}

C++题解+代码
http://www.cnblogs.com/937337156Zhang/p/6044230.html

记忆化搜索即可代码如下（c++）:
#include<bits/stdc++.h>
using namespace std;
const int dx[4]= {-1,0,1,0 };
const int dy[4]= {0,-1,0,1 };
struct edge {
int x,y,value; } b[250010];
inline bool cmp(const edge &a,const edge &b) {
return a.value>b.value; }
int dp[510][510],r,c,h,j,a[510][510],ans;
int main() {
scanf("%d %d",&r,&c);
for(int i=1; i<=r; i++)
for(int d=1; d<=c; d++) {
b[++j].x=i;
b[j].y=d;
scanf("%d",&b[j].value);
a[i][d]=b[j].value; }
sort(b+1,b+1+r*c,cmp);
for(int i=1; i<=r*c; i++) {
register int x=b[i].x;
register int y=b[i].y;
for(int w=0; w<4; w++)
if(a[x+dx[w]][y+dy[w]]<a[x][y])
dp[x+dx[w]][y+dy[w]]=max(dp[x+dx[w]][y+dy[w]],dp[x][y]+1); }
for(int i=1; i<=r; i++)
for(int j=1; j<=c; j++)
ans=max(ans,dp[i][j]+1);
cout<<ans; }

#include<iostream>
#include<algorithm>
#include<cmath>
#include<string.h>
long long o[550][550]={0};
long long f[550][550]={0};
using namespace std;
int way(int x,int y)
{
long long tol=0;
if(o[x][y]>o[x-1][y]&&o[x-1][y]!=-1){
if(f[x-1][y]==0) f[x-1][y]=way(x-1,y)+1;
tol=max(tol,f[x-1][y]);
}
if(o[x][y]>o[x+1][y]&&o[x+1][y]!=-1){
if(f[x+1][y]==0) f[x+1][y]=way(x+1,y)+1;
tol=max(tol,f[x+1][y]);
}

if(o[x][y]>o[x][y-1]&&o[x][y-1]!=-1){
if(f[x][y-1]==0) f[x][y-1]=way(x,y-1)+1;
tol=max(tol,f[x][y-1]);
}

if(o[x][y]>o[x][y+1]&&o[x][y+1]!=-1){
if(f[x][y+1]==0) f[x][y+1]=way(x,y+1)+1;
tol=max(tol,f[x][y+1]);
}

return tol;
}
int main()
{
long long n,m;
cin>>n>>m;
memset(o,-1,sizeof(o));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>o[i][j];
long long maxw=-233333;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(f[i][j]==0) f[i][j]=way(i,j)+1;
maxw=max(maxw,f[i][j]);
}
}

cout<<maxw;
return 0;
}
//为什么会错啊

动态规划为什么80分？
#include <stdio.h>
#include <algorithm>
#include <cmath>
using namespace std;
struct node
{
int x;
int y;
int v;
};
node m[200000];
int maxn[500][1500];
int cmp(const node &a,const node &b)
{
if (a.v<b.v) return 1;
else return 0;
}
int main()
{
int r,c;
int tot=0;
scanf("%d%d",&r,&c);

for (int i=1;i<=r;i++)
for (int j=1;j<=c;j++)
{
int n;
scanf("%d",&n);
tot=tot+1;
m[tot].x=i;
m[tot].y=j;
m[tot].v=n;
}
sort(m+1,m+r*c+1,cmp);
int ma=0;
int to=0;
for (int i=1;i<=r;i++)
for (int j=1;j<=c;j++)
{
to=to+1;
int xx=m[to].x;
int yy=m[to].y;
maxn[xx][yy]=max(max(max(maxn[xx+1][yy]+1,maxn[xx][yy+1]+1),maxn[xx-1][yy]+1),maxn[xx][yy-1]+1);
if (maxn[xx][yy]>=ma) ma=maxn[xx][yy];
}
printf("%d",ma);
return 0;
}

#include<bits/stdc++.h>
using namespace std;
int num[502][502],opt[502][502],r,c,ans;
int dx[4]= {0,1,0,-1};
int dy[4]= {1,0,-1,0};
int trav(int x,int y)
{
int k,nx,ny,maxl;
if (opt[x][y]>0)
return opt[x][y];//如果这个位置已经走过，直接返回此位置的值（防止冗余计算）
for(k=0; k<4; k++)
{
nx=x+dx[k];
ny=y+dy[k];
if (num[nx][ny]<num[x][y]&&opt[nx][ny]==0)
opt[nx][ny]=trav(nx,ny)+1;
}//向四个方向找，如果满足题目条件并且没走过，更新此位置
maxl=0;
for(k=0; k<4; k++)
{
nx=x+dx[k];
ny=y+dy[k];
if (num[nx][ny]<num[x][y])
maxl=max(opt[nx][ny],maxl);//把四个方向中满足条件且最大的值保存下来
}
return maxl;
}
int main()
{
int i,j;
// freopen("ski.in","r",stdin);
// freopen("ski.out","w",stdout);
cin>>r>>c;
for(i=0; i<=r+1; i++)
for(j=0; j<=c+1; j++)
{
num[i][j]=10001;//设置框架
opt[i][j]=0;//opt数组清零
}
for(i=1; i<=r; i++)
for(j=1; j<=c; j++)
cin>>num[i][j];
ans=0;//答案清零
for(i=1; i<=r; i++)
for(j=1; j<=c; j++)
{
if (opt[i][j]==0)//如果没走过
opt[i][j]=trav(i,j)+1;//当前位置为能到达此位置的最大点+1（即为到此位置的最大长度）
ans=max(ans,opt[i][j]);//保存最大长度
}
cout<<ans<<endl;
// fclose(stdin);
// fclose(stdout);
}

#include<bits/stdc++.h>
using namespace std;
int num[502][502],opt[502][502],r,c,ans;
int dx[4]= {0,1,0,-1};
int dy[4]= {1,0,-1,0};
int trav(int x,int y)
{
int k,nx,ny,maxl;
if (opt[x][y]>0)
return opt[x][y];
for(k=0; k<4; k++)
{
nx=x+dx[k];
ny=y+dy[k];
if (num[nx][ny]<num[x][y]&&opt[nx][ny]==0)
opt[nx][ny]=trav(nx,ny)+1;
}
maxl=0;
for(k=0; k<4; k++)
{
nx=x+dx[k];
ny=y+dy[k];
if (num[nx][ny]<num[x][y])
maxl=max(opt[nx][ny],maxl);
}
return maxl;
}
int main()
{
int i,j;
// freopen("ski.in","r",stdin);
// freopen("ski.out","w",stdout);
cin>>r>>c;
for(i=0; i<=r+1; i++)
for(j=0; j<=c+1; j++)
{
num[i][j]=10001;
opt[i][j]=0;
}
for(i=1; i<=r; i++)
for(j=1; j<=c; j++)
cin>>num[i][j];
ans=0;
for(i=1; i<=r; i++)
for(j=1; j<=c; j++)
{
if (opt[i][j]==0)
opt[i][j]=trav(i,j)+1;
ans=max(ans,opt[i][j]);
}
cout<<ans<<endl;
// fclose(stdin);
// fclose(stdout);
}

uses math;
var map,dp:array[0..500,0..500] of longint;
  r,c,i,j,ans:longint;

function search(x,y:longint):longint;
var res:longint;
begin
  res:=1;
  if dp[x,y]<>0 then exit(dp[x,y]);
  if (x>1) and (map[x-1,y]<map[x,y]) then res:=max(res,search(x-1,y)+1);
  if (y>1) and (map[x,y-1]<map[x,y]) then res:=max(res,search(x,y-1)+1);
  if (x<r) and (map[x+1,y]<map[x,y]) then res:=max(res,search(x+1,y)+1);
  if (y<c) and (map[x,y+1]<map[x,y]) then res:=max(res,search(x,y+1)+1);
  dp[x,y]:=res;
  exit(res);
end;

begin
  read(r,c);
  for i:=1 to r do
    for j:=1 to c do
      read(map[i,j]);
  ans:=1;
  fillchar(dp,sizeof(dp),0);

  for i:=1 to r do
    for j:=1 to c do
      ans:=max(ans,search(i,j));
  write(ans);
end.

测试数据 #0: Accepted, time = 125 ms, mem = 5520 KiB, score = 10
测试数据 #1: Accepted, time = 31 ms, mem = 5520 KiB, score = 10
测试数据 #2: Accepted, time = 46 ms, mem = 5524 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 5520 KiB, score = 10
测试数据 #4: Accepted, time = 78 ms, mem = 5520 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 5520 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 5520 KiB, score = 10
测试数据 #7: Accepted, time = 46 ms, mem = 5524 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 5524 KiB, score = 10
测试数据 #9: Accepted, time = 109 ms, mem = 5516 KiB, score = 10
Accepted, time = 480 ms, mem = 5524 KiB, score = 100
http://www.cnblogs.com/Coolxxx/p/5348117.html

http://www.cnblogs.com/oierforever/p/4764152.html

简单的记忆化搜索就很快的
#include<cstdio>
#include<cstring>
using namespace std;
const int hang[]={-1,0,1,0},lie[]={0,1,0,-1};
int done[501][501],h[501][501],r,c;
int f(int x,int y)
{
if(done[x][y]!=-1)
return done[x][y];
done[x][y]=1;
for(int i=0;i<=3;i++)
{
int nx=x+hang[i];
int ny=y+lie[i];
if(h[nx][ny]<h[x][y]&&nx>=1&&nx<=r&&ny>=1&&ny<=c)
{
int l1=f(nx,ny)+1;
if(l1>done[x][y])
done[x][y]=l1;
}
}
return done[x][y];
}
int main()
{
int ans;
scanf("%d%d",&r,&c);
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
scanf("%d",&h[i][j]);
ans=0;
memset(done,-1,sizeof(done));
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
{
int l=f(i,j);
if(l>ans)
ans=l;
}
printf("%d",ans);
return 0;
}

#include<iostream>
#include<cstring>
using namespace std;

int d[505][505]={0},a[505][505],n,m,ans=0;

int dp(int i,int j) {
int &ans=d[i][j],v=a[i][j];
if (ans) return ans;
ans=1;
if (i+1<n) if (v>a[i+1][j]) ans=max(ans,dp(i+1,j)+1);
if (i-1>=0) if (v>a[i-1][j]) ans=max(ans,dp(i-1,j)+1);
if (j+1<m) if (v>a[i][j+1]) ans=max(ans,dp(i,j+1)+1);
if (j-1>=0) if (v>a[i][j-1]) ans=max(ans,dp(i,j-1)+1);
return ans;
}

int main() {
cin>>n>>m;
for (int i=0;i<n;++i)
for (int j=0;j<m;++j) cin>>a[i][j];
for (int i=0;i<n;++i)
for (int j=0;j<m;++j) if (!d[i][j]) dp(i,j);
for (int i=0;i<n;++i)
for (int j=0;j<m;++j) if (d[i][j]>ans) ans=d[i][j];
cout<<ans;
return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=502;
int f[maxn][maxn];
int k[maxn][maxn];
bool vis[maxn][maxn];
int numh,numl;
int dh[4]={0,0,1,-1},dl[4]={1,-1,0,0};
int dfs(int h,int l)
{
if(vis[h][l])return f[h][l];
else
{
for(int i=0;i<4;i++)
if(h+dh[i]>=1&&l+dl[i]>=1&&h+dh[i]<=numh&&l+dl[i]<=numl&&k[h+dh[i]][l+dl[i]]<k[h][l])
f[h][l]=max(f[h][l],dfs(h+dh[i],l+dl[i])+1);
vis[h][l]=true;
return f[h][l];
}
}
int main()
{
memset(vis,false,sizeof(false));
scanf("%d%d",&numh,&numl);
for(int i=1;i<=numh;i++)
for(int j=1;j<=numl;j++)
scanf("%d",&k[i][j]);
int maxx=-1;
for(int i=1;i<=numh;i++)
for(int j=1;j<=numl;j++)
maxx=max(maxx,dfs(i,j));
printf("%d\n",maxx+1);
return 0;
}
样例略坑。。我写了个spfa才发现不对
应该是记忆化搜索