uva 10285 Longest Run on a Snowboard

기초 DP 복습, 기억화 검색
제목: 이름과 n*m 행렬을 주십시오. 다음은 행렬 정보입니다. 매번 한 칸에서 상하좌우로 이동할 수 있지만 그 숫자는 현재 있는 칸보다 작아야 합니다.임의의 점에서 출발해서 가장 긴 거리가 얼마냐고 물어볼 수 있다
dp[i][j]는 (i,j)에서 출발할 수 있는 가장 긴 길을 나타낸다
dp[i][j]=max{dp[x][y]}+1, 그중 (x, y)는 (i, j) 부근의 네 칸 중 하나이고 a[x][y]

#include <cstdio>

#include <cstring>

#define N 110

#define MAX 110

#define max(a,b) ((a)>(b)?(a):(b))



const int x[4]={-1,1,0,0}; //    

const int y[4]={0,0,-1,1}; //    

int a[N][N];

int dp[N][N];

int n,m;



int dfs(int i, int j)

{

   if(dp[i][j] != -1)

      return dp[i][j];



   dp[i][j] = 0;

   for(int k=0; k<4; k++) //4   

   {

      int xx = i + x[k];

      int yy = j + y[k];

      if(a[xx][yy] < a[i][j])

         dp[i][j] = max(dp[i][j] , dfs(xx,yy));

   }

   return ++dp[i][j];

}



int main()

{

   int cas;

   scanf("%d",&cas);

   while(cas--)

   {

      char name[50];

      scanf("%s%d%d",name,&n,&m);

      for(int i=1; i<=n; i++)

         for(int j=1; j<=m; j++)

            scanf("%d",&a[i][j]);

      for(int i=0; i<=m+1; i++)

         a[0][i] = a[n+1][i] = MAX;

      for(int i=0; i<=n+1; i++)

         a[i][0] = a[i][m+1] = MAX;



      memset(dp,-1,sizeof(dp));

      int res = -1;

      for(int i=1; i<=n; i++)

         for(int j=1; j<=m; j++)

            res = max(res , dfs(i,j));



      printf("%s: %d
",name,res);

   }

   return 0;

}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

기초 DP 복습, 기억화 검색 제목: 이름과 n*m 행렬을 주십시오. 다음은 행렬 정보입니다. 매번 한 칸에서 상하좌우로 이동할 수 있지만 그 숫자는 현재 있는 칸보다 작아야 합니다.임의의 점에서 출발해서 가장 긴 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

uva 10285 Longest Run on a Snowboard

좋은 웹페이지 즐겨찾기