| ||||||||||
| 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