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

## 记忆化DP

Posted by Antinomy at 2016-12-09 17:27:52 on Problem 1088
```#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: