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