> 这个题我觉得自己写的程序可以得到正确的结果啊，可结果是Wrong Answer。可以帮俺
> 看看有什么没考虑周全么？谢谢。另外，如果我做的程序即超时又错误，那么会被判作
> 什么？即Time Limit Exceed和Wrong Answer哪个优先级更高？
> 
> 滑雪
> 
> Time Limit:1000MS  Memory Limit:65536K
> Total Submit:2517 Accepted:612 
> 
> Description 
> Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域
> 必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。
> Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代
> 表点的高度。下面是一个例子 
> 
> 
>  1  2  3  4 5
> 16 17 18 19 6
> 15 24 25 20 7
> 14 23 22 21 8
> 13 12 11 10 9
> 
> 一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子
> 中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最
> 长的一条。
> 
> Input 
> 输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整
> 数，代表高度h，0<=h<=10000。
> 
> Output 
> 输出最长区域的长度。
> 
> Sample Input 
> 
> 5 5
> 1 2 3 4 5
> 16 17 18 19 6
> 15 24 25 20 7
> 14 23 22 21 8
> 13 12 11 10 9
> 
> 
> Sample Output 
> 
> 25
> 
> Source 
> Don't know
> 
> 程序：
> #include <iostream>
> using namespace std;
> 
> //define the level status of link
> #define HIGH 1
> #define EDGE 0
> #define LOW  -1
> #define DIMENSION 100
> 
> int nColNum, nRowNum;
> int Area[DIMENSION][DIMENSION];
> 
> typedef struct _LinkStatus
> {
> 	int nLeft;
> 	int nTop;
> 	int nRight;
> 	int nBottom;
> } LinkStatus;
> 
> LinkStatus status[DIMENSION][DIMENSION];
> 
> void InitLinkStatus()
> {
> 	int i, j;
> 	int xTail = nColNum - 1;
> 	int yTail = nRowNum - 1;
> 	///////////////////////////////////////////////////////////////////
> ///////
> 	// initialize four edges
> 	for(i = 0; i < nRowNum; i++)
> 	{	// initialize the left line
> 		status[0][i].nLeft = EDGE;
> 	}
> 
> 	for(i = 0; i < nColNum; i++)
> 	{	// initialize the top line
> 		status[i][0].nTop = EDGE;
> 	}
> 
> 	for(i = 0; i < nRowNum; i++)
> 	{	// initialize the right line
> 		status[xTail][i].nRight = EDGE;
> 	}
> 
> 	for(i = 0; i < nColNum; i++)
> 	{	// initialize the bottom line
> 		status[i][yTail].nBottom = EDGE;
> 	}
> 
> 	///////////////////////////////////////////////////////////////////
> ///////
> 	// initialize horizontally
> 	for(i = 0; i < nRowNum; i++)
> 	{
> 		for(j = 0; j < xTail; j++)
> 		{
> 			if(Area[j][i] > Area[j + 1][i])
> 			{
> 				status[j][i].nRight = HIGH;
> 				status[j + 1][i].nLeft = LOW;
> 			}
> 			else if(Area[j][i] < Area[j + 1][i])
> 			{
> 				status[j][i].nRight = LOW;
> 				status[j + 1][i].nLeft = HIGH;
> 			}
> 			else
> 			{
> 				status[j][i].nRight = LOW;
> 				status[j + 1][i].nLeft = LOW;
> 			}
> 		}
> 	}
> 
> 	///////////////////////////////////////////////////////////////////
> ///////
> 	// initialize vertically
> 	for(j = 0; j < nColNum; j++)
> 	{
> 		for(i = 0; i < xTail; i++)
> 		{
> 			if(Area[j][i] > Area[j][i + 1])
> 			{
> 				status[j][i].nBottom = HIGH;
> 				status[j][i + 1].nTop = LOW;
> 			}
> 			else if(Area[j][i] < Area[j][i + 1])
> 			{
> 				status[j][i].nBottom = LOW;
> 				status[j][i + 1].nTop = HIGH;
> 			}
> 			else
> 			{
> 				status[j][i].nBottom = LOW;
> 				status[j][i + 1].nTop = LOW;
> 			}
> 		}
> 	}
> }
> 
> // return the longest path starting from the area(x, y)
> int GetLongestPath(int x, int y)
> {
> 	int nMax, nTemp;
> 	nMax = 0;
> 	//test each path
> 	if(status[x][y].nLeft == HIGH)
> 	{
> 		nTemp = GetLongestPath(x - 1, y);
> 		if(nMax < nTemp)
> 		{
> 			nMax = nTemp;
> 		}
> 	}
> 
> 	if(status[x][y].nTop == HIGH)
> 	{
> 		nTemp = GetLongestPath(x, y - 1);
> 		if(nMax < nTemp)
> 		{
> 			nMax = nTemp;
> 		}
> 	}
> 
> 	if(status[x][y].nRight == HIGH)
> 	{
> 		nTemp = GetLongestPath(x + 1, y);
> 		if(nMax < nTemp)
> 		{
> 			nMax = nTemp;
> 		}
> 	}
> 
> 	if(status[x][y].nBottom == HIGH)
> 	{
> 		nTemp = GetLongestPath(x, y + 1);
> 		if(nMax < nTemp)
> 		{
> 			nMax = nTemp;
> 		}
> 	}
> 	// if the current point is a valley, nMax keeps 0
> 	return nMax + 1;
> }
> int main()
> {
> 	int i, j, nMax, nTemp;
> 
> 	//load the input information
> 	cin>>nRowNum>>nColNum;
> 	for(i = 0; i < nRowNum; i++)
> 		for(j = 0; j < nColNum; j++)
> 			cin>>Area[j][i];
> 	
> 	InitLinkStatus();
> 	
> 	nMax = 1;
> 	for(i = 0; i < nRowNum; i++)
> 	{
> 		for(j = 0; j < nColNum; j++)
> 		{
> 			//only a peak needs to trace as the start 
> point
> 			if((status[j][i].nLeft > LOW) &&
> 			   (status[j][i].nTop  > LOW) &&
> 			   (status[j][i].nRight > LOW) &&
> 			   (status[j][i].nBottom > LOW))
> 			{
> 				nTemp = GetLongestPath(j, i);
> 				if(nMax < nTemp)
> 				{
> 					nMax = nTemp;
> 				}
> 			}
> 		}
> 	}
> 
> 	//output the result
> 	cout<<nMax<<endl;
> 	return 0;
> }

• 难到可以改成nlogn的？如果能我努力试试改改。 (46) speedfirst 2005-08-13 12:45:47
  • 我说的是AC的代码大部分是n^2:),你的还不是 (52) c0500448242 2005-08-13 12:46:47
    • 再加三行就n^2了 (0) T3 2005-08-13 12:52:23
      • ... (0) c0500448242 2005-08-13 12:52:39
      • 有什么优化的建议么？ (0) speedfirst 2005-08-13 12:55:44