Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 为什么要递归呢 直接数长度是不是更简单 ?

Posted by KoB at 2015-07-14 11:59:18 on Problem 1088
```// 懒 于是直接数长度 从大到小数完了事
// 同上 于是没优化 渣代码 希望还能读

#include <cstdio>
#include <cstring>
#include <algorithm>

struct Pos {
int val;
int u;
int v;
Pos() {}
Pos(int _val, int _u, int _v) : val(_val), u(_u), v(_v) {}
};

int cmp(Pos a, Pos b) { return a.val > b.val; }

int main() {
int row, col;
scanf("%d %d", &row, &col);
int mat[row][col];
for (int i=0; i<row; i++)
for (int j=0; j<col; j++)
scanf("%d", &(mat[i][j]));

Pos pos[row*col];
for (int i=0; i<row; i++)
for (int j=0; j<col; j++)
pos[i*col+j] = Pos(mat[i][j], i, j);

std::sort(pos, pos+row*col, cmp);

int dist[row][col];
memset(dist, 0, sizeof(dist));

for (int it=0; it<row*col; it++) {
int i = pos[it].u;
int j = pos[it].v;
if (i != 0       && mat[i][j] > mat[i-1][j]) dist[i-1][j] = std::max(dist[i-1][j], dist[i][j] + 1);
if (i != row - 1 && mat[i][j] > mat[i+1][j]) dist[i+1][j] = std::max(dist[i+1][j], dist[i][j] + 1);
if (j != 0       && mat[i][j] > mat[i][j-1]) dist[i][j-1] = std::max(dist[i][j-1], dist[i][j] + 1);
if (j != col - 1 && mat[i][j] > mat[i][j+1]) dist[i][j+1] = std::max(dist[i][j+1], dist[i][j] + 1);
}

int length = 0;
for (int i=0; i<row; i++)
for (int j=0; j<col; j++)
if (dist[i][j] > length)
length = dist[i][j];

printf("%d\n", length+1);

return 0;
}
```

Followed by: