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:记忆化DP

Posted by happy_Michael at 2019-07-21 16:23:02 on Problem 1088
In 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:
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