[동적 계획] UVA10285 - Longest Run on a Snowboard

Problem C
Longest Run on a Snowboard
Input: standard input
Output: standard output
Time Limit: 5 seconds
Memory Limit: 32 MB
 
Michael likes snowboarding. That's not very surprising, since snowboarding is really great. The bad thing is that in order to gain speed, the area must slide downwards. Another disadvantage is that when you've reached the bottom of the hill you have to walk up again or wait for the ski-lift.
Michael would like to know how long the longest run in an area is. That area is given by a grid of numbers, defining the heights at those points. Look at this example:

 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

One can slide down from one point to a connected other one if and only if the height decreases. One point is connected to another if it's at left, at right, above or below it. In the sample map, a possible slide would be 24-17-16-1 (start at 24, end at 1). Of course if you would go 25-24-23-...-3-2-1, it would be a much longer run. In fact, it's the longest possible.
Input
The first line contains the number of test cases N. Each test case starts with a line containing the name (it's a single string), the number of rows R and the number of columns C. After that follow R lines with C numbers each, defining the heights. R and C won't be bigger than 100, N not bigger than 15 and the heights are always in the range from 0 to 100.
For each test case, print a line containing the name of the area, a colon, a space and the length of the longest run one can slide down in that area.

Sample Input

2

Feldberg 10 5

56 14 51 58 88

26 94 24 39 41

24 16 8 51 51

76 72 77 43 10

38 50 59 84 81

5 23 37 71 77

96 10 93 53 82

94 15 96 69 9

74 0 62 38 96

37 54 55 82 38

Spiral 5 5

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

 
Sample Output

Feldberg: 7

Spiral: 25

(Math Lovers’ Contest, Problem Setter: Stefan Pochmann)
 
제목:
마이클은 스키를 아주 좋아해요.스키는 재미있지만 좀 귀찮아요.속도를 얻기 위해서는 높은 곳에서 낮은 곳으로 스키를 타야 한다.산기슭에 도착하면 걸어서 산에 오르거나 스키 등산 케이블카를 기다려야 한다.
마이클은 어느 스키장에서 가장 긴 스키 경로가 얼마나 긴지 알고 싶어 한다.스키장 구역은 숫자로 이루어진 네모난 블록으로 표시된다.숫자의 크기는 각 점의 높이를 대표한다.다음 예를 참조하십시오.

 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(24부터 시작해서 1로 끝낼 수 있다).그럼요. 25-24-23-22-를 타려면...3-2-1도 괜찮아요. 이게 이전 경로보다 훨씬 길어요.사실 이것도 가장 긴 경로다.
사고방식:DAG의 동태적인 기획은 방향이 상하좌우 네 방향으로 바뀌었을 뿐 상태 이동 공식은 변화가 없다.

#include
#include

using namespace std;

int map[110][110],vis[110][110],arry[110][110];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,m;

int dp(int x,int y)
    {
        if(vis[x][y]) return arry[x][y];
        for(int i=0;i<4;i++)
            {
                int dx=x+dir[i][0],dy=y+dir[i][1];
                if(dx>=0&&dx=0&&dy>num;
        while(num--)
            {
                string name;
                cin>>name>>n>>m;
                memset(map, 0, sizeof(map));
                memset(vis, 0, sizeof(vis));
                for(int i=0;i>map[i][j];
                                arry[i][j]=0;
                            }
                    }
                int maxn=0;
                for(int i=0;imaxn) maxn=cnt;
                            }
                    }
                cout<