Poj 1088スキー(クラシックダイナミックプランニング)

とっくにこの問題を見て、長い間考えていたが、実現しなかった.それから他の人のコードを見て、古典的なダイナミックな計画だと言ったが、私はまだ分からない.しばらくしてまた自分で長い間考えて、やっとコードを書いて、コードは3000 Bがあって、北京大学で運行する時間も200+MSで、それからまた一回の他の人の動態の計画のコードを見て、ついにどのように規則を理解して、それから自分で他の人のコードによってまた1つの動態の計画のコードを書き直して、コードは以下のようにして、運行時間は0 MSです.(え....やはりダイナミックな企画の方が意味がはっきりしていますね.)

/**    ：DP[i][j] = Max{ DP[i-1][j], DP[i+1][j], DP[i][j-1], DP[i][j+1] } + 1;**/
#include <stdio.h>

int r, c, map[101][101], dp[101][101], MAX;

int DP(int x, int y)
{
    int i, x0, y0, max=0, dir[4][2]={1,0,-1,0,0,1,0,-1};

    if (dp[x][y]) return dp[x][y];

    for (i=0; i<4; i++)
    {
        x0 = x + dir[i][0];
        y0 = y + dir[i][1];
        if (x0<0 || y0<0 || x0>=r || y0>=c) continue;
        if (map[x0][y0]<map[x][y] && DP(x0, y0)>max) max = dp[x0][y0];
    }
    dp[x][y] = max + 1;
    return dp[x][y];
}

int main()
{
    int i, j;

    scanf("%d %d", &r, &c);
    for (i=0; i<r; i++)
      for (j=0; j<c; j++)
        scanf("%d", &map[i][j]);
    for (i=0; i<r; i++)
      for (j=0; j<c; j++)
      {
          DP(i, j);
          if (dp[i][j] > MAX) MAX = dp[i][j];
      }
    printf("%d/n", MAX);
}