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
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

Re:非常经典的动态规划,用递归下的记忆化搜索来实现。我将整个实现流程和很多容易错的地方都注释起来,希望能够对那些比较困惑的朋友有所帮助。这程序花了我半个小时调试和写注释,题不在多,经典则行。好晚了,好累,睡觉~~

Posted by tankadozmy at 2010-02-01 22:18:38 on Problem 1088
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:
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