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

各位大牛,所有变态数据我都过了就还是WA,谁帮我看看,先排序后DP的

Posted by chenzeyu at 2010-01-19 19:43:57 on Problem 1088
#include<iostream>
#include<algorithm>
#include<cmath>

using namespace std;
#define MAX  100 + 10

int arr[MAX][MAX];
int dp[MAX][MAX];
int maximun = -2147483647;

struct map
{
	int h;
	int x;
	int y;
};
bool cmp_map(map a, map b)
{
	return a.h < b.h;
}
//判断坐标是否是在上下左右4点
bool coordinate(map a,map b)
{
	if(abs(a.y - b.y) == 0 && abs(a.x - b.x) == 1)	return true;
	if(abs(a.y - b.y) == 1 && abs(a.x - b.x) == 0)	return true;
		return false;
}
int main()
{
	memset(dp,0,sizeof(dp));
	int x,y;
	cin >> x >> y;
	
	for(int i = 1;i <= x;++i)
		for(int j = 1;j <= y; ++j)
			cin >> arr[i][j];
	
	map matrix[MAX * MAX];
	for(int i = 1;i <= x;++i)
		for(int j = 1;j <= y;++j)
		{
			matrix[(i - 1) * y + j].h = arr[i][j];
			matrix[(i - 1) * y + j].x = i;
			matrix[(i - 1) * y + j].y = j;
		}
	sort(matrix + 1,matrix + x * y + 1 ,cmp_map);//排序

	for(int i = 1; i <= x * y; ++i)
	{
		for(int j = i + 1;j <= x * y; ++j)
		{
			if(coordinate(matrix[i],matrix[j]) && matrix[j].h > matrix[i].h )//坐标合理并且有高度差
				dp[matrix[j].x][matrix[j].y] = dp[matrix[i].x][matrix[i].y] + 1;
		}
	}
	
	for(int i = 1;i <= x; ++i)
		for(int j = 1;j <= y; ++j)
		{
			if(dp[i][j] > maximun)
				maximun = dp[i][j];
		}
		cout << maximun + 1<< endl;
					
	return 0;
}

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