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

做的第一道DP,一次AC

Posted by jasonnk at 2008-03-31 19:51:54 on Problem 1088
#include <iostream>
#include <cstdlib>
#include <cmath>

using namespace std;

int a[101][101];
int temp[101][101];
int most=0;
int r,c;

int getMaxPath(int i,int j){
	if((i==0)||(j==0)||(i>r)||(j>c)) return 0;
	int max1 = 0;
	int curValue = a[i][j];
	if(temp[i][j]!=-1) return temp[i][j];
	if(curValue>a[i-1][j]) max1 = getMaxPath(i-1,j);
	if(curValue>a[i+1][j]) max1 = max1>getMaxPath(i+1,j)?max1:getMaxPath(i+1,j);
	if(curValue>a[i][j-1]) max1 = max1>getMaxPath(i,j-1)?max1:getMaxPath(i,j-1);
	if(curValue>a[i][j+1]) max1 = max1>getMaxPath(i,j+1)?max1:getMaxPath(i,j+1);
	
	max1++;
	
	temp[i][j] = max1;
	if(most < max1) most=max1;
	return max1;
}

int main() {
	memset(a,-1,101*101);
	cin >> r >> c;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			cin >> a[i][j];
			temp[i][j] = -1;
		}
	}
	
	for(int i=1;i<=r;i++){
			for(int j=1;j<=c;j++){
				getMaxPath(i,j);
			}
		}
	
	cout << most << 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