为何90(第二个点超时)

P1434 [SHOI2002] 滑雪

Gypsophila @ 2017-10-24 18:13:50

RT.

#include <iostream>

using namespace std;
int n, m, ans = -1;
int a[105][105];
int max_line[105][105];
int d1[10] = {1, -1, 0, 0}, d2[10] = {0, 0, 1, -1};

void DFS(int i, int j, int now_line)
{
     if(max_line[i][j] == 0) return ;
     //cout << i << " " << j << endl;
     if(now_line < max_line[i][j]) return ;
     max_line[i][j] = now_line;
     for(int k = 0; k < 4; k++)
     {
         int A = i + d1[k];
         int B = j + d2[k];
         if(a[A][B] < a[i][j])
            DFS(A, B, now_line + 1);
     }
     return ;
     //cout << endl;
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            max_line[i][j] = 1;
        }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            DFS(i, j, max_line[i][j]);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
                ans = max(ans, max_line[i][j]);
    cout << ans << endl;
   // system("PAUSE");
    return 0;
}

by bymlg001 @ 2017-10-24 19:03:56

您实际上并没有用到记忆化搜索,只是存起来了(假的记忆化搜索),而且ans在dfs的时候更新就好。不用单独n^2找。


|