| ||||||||||
| 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 | |||||||||
做的第一道DP,一次AC#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator