Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:为什么要递归呢 直接数长度是不是更简单 ?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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator