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

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

Posted by whxc049 at 2015-08-01 20:51:34 on Problem 1088
In Reply To:为什么要递归呢 直接数长度是不是更简单 ? Posted by:KoB at 2015-07-14 11:59:18
> // 懒 于是直接数长度 从大到小数完了事
> // 同上 于是没优化 渣代码 希望还能读
> 
> #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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator