Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 81099		Accepted: 30239

Description

Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子 

1  2  3  4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。

Input

输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。

Output

输出最长区域的长度。

Sample Input

5 51 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9

Sample Output

25

Source

 

在NYOJ上就能AC，在poj就一直WA，原来对于二维数组中的两个大小相同的值，是不能移动到的，，（各方数据不同的原因）

/*times  memy 79ms    304k by orc */#include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;int R, C;int d[105][105], mat[105][105];//d[i][j]为从第i行第j列的位置开始出发所得到的最长路int dir[][2] = {
     {-1,0},{
     0,-1},{
     1,0},{
     0,1}};int dp(int i,int j){    //printf("[%d],[%d],%d\n",i,j,s);    if(i < 1 || i > R || j < 1 || j > C) return 0;    int& res = d[i][j];    if(res != -1) return res;    res = 1;    for(int k = 0 ; k < 4; ++k)    {        int ti = i + dir[k][0], tj = j + dir[k][1];        if(mat[i][j] > mat[ti][tj]){
     //这里wa了很多次，mat[i][j]必须 > mat[ti][tj]，而不能 >=        res = max(res,dp(ti,tj) + 1);        }    }    return res;}void getans(){    for(int i = 1; i <= R; ++i)        for(int j = 1; j <= C; ++j)            dp(i,j);}int main(){    ios::sync_with_stdio(0);        cin >> R >> C;        for(int i  = 1; i <= R; ++i)        for(int j = 1; j <= C ; ++j)        cin >> mat[i][j];        memset(d,-1,sizeof d);        getans();        // d[3][3] = dp(3, 3, mat[3][3]);        int ans = 0;        for(int i = 1; i <= R; ++i)            for(int j = 1; j <= C; ++j)            ans = max(ans,d[i][j]);            cout << ans << endl;   // }}