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 |
Re:非常经典的动态规划,用递归下的记忆化搜索来实现。我将整个实现流程和很多容易错的地方都注释起来,希望能够对那些比较困惑的朋友有所帮助。这程序花了我半个小时调试和写注释,题不在多,经典则行。好晚了,好累,睡觉~~In Reply To:非常经典的动态规划,用递归下的记忆化搜索来实现。我将整个实现流程和很多容易错的地方都注释起来,希望能够对那些比较困惑的朋友有所帮助。这程序花了我半个小时调试和写注释,题不在多,经典则行。好晚了,好累,睡觉~~ Posted by:gfedcba at 2009-02-28 03:37:51 楼主你确定你没有TLE? 我的更清楚一点吧……而且没用cnt[][]……注释是测数据时留下的,就当没有吧 #include<iostream> // 26?? #include<fstream> #include<stack> #define N 100 using namespace std; void dfs(int,int); struct point { int h; }p[N][N]; stack <point> s; int r,c; int len=0,t_len=0; int main() { cin>>r>>c; int i,j; // ifstream fcin; // fcin.open("text.dat"); for(i=0;i<r;i++) for(j=0;j<c;j++) { //fcin>>p[i][j].h; cin>>p[i][j].h; } for(i=0;i<r;i++) for(j=0;j<c;j++) { s.push(p[i][j]); dfs(i,j); while(!s.empty()){s.pop();} if(t_len>len) len=t_len; } cout<<len-1<<endl; //26-1? // fcin.close(); return 0; } void dfs(int i,int j) { if(i<0||j<0||i==r||j==c) { if(s.size()>t_len) t_len=s.size(); return; } else if(p[i-1][j].h<s.top().h) { s.push(p[i-1][j]); dfs(i-1,j); s.pop(); } else if(p[i][j-1].h<s.top().h) { s.push(p[i][j-1]); dfs(i,j-1); s.pop(); } else if(p[i+1][j].h<s.top().h) { s.push(p[i+1][j]); dfs(i+1,j); s.pop(); } else if(p[i][j+1].h<s.top().h) { s.push(p[i][j+1]); dfs(i,j+1); s.pop(); } else { if(s.size()>t_len) t_len=s.size(); return; } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator