| ||||||||||
| 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:记忆化DPIn Reply To:记忆化DP Posted by:Antinomy at 2016-12-09 17:27:52 > #include<iostream>
> #include<iomanip>
> #include<cstring>
> #include<vector>
> #include<sstream>
> #include<algorithm>
> #include<string>
> #include<cstdio>
> #include<math.h>
> #include<map>
> #include<cctype>
> #include<queue>
> #include<functional>
> #include<set>
> #define maxn 110
> #define min(a,b) (a)>(b)?(b):(a)
> #define Mem(a,b) memset((a),(b),sizeof((a)))
> using namespace std;
> #include<iostream>
> #include<cstdio>
> #include<cstdlib>
> #include<cmath>
> using namespace std;
> int R, C, G[maxn][maxn], num[maxn][maxn],vis[maxn][maxn];
> const int dx[] = { 0, 0, 1, -1 };
> const int dy[] = { 1, -1, 0, 0 };
> int dp(int x, int y){
> if (vis[x][y]) return num[x][y];
> for (int i = 0; i < 4; i += 1)
> {
> int nx = x + dx[i], ny = y + dy[i];
> if (nx > 0 && nx <= R && ny > 0 && ny <= C && G[nx][ny]<G[x][y]){
> num[x][y] = max(num[x][y], dp(nx, ny) + 1);
> }
> }
> vis[x][y] = 1;
> return num[x][y];
> }
> int main(){
> cin >> R >> C;
> for (int i = 1; i <= R; i += 1){
> for (int j = 1; j <= C; j += 1)
> cin >> G[i][j];
> }
> Mem(vis, 0);
> Mem(num, 0); int ans = 0;
> for (int i = 1; i <= R; i += 1){
> for (int j = 1; j <= C; j += 1)
> ans = max(dp(i, j), ans);
> }
> cout << ans + 1<< endl;
> return 0;
> }
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator