| ||||||||||
| 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 | |||||||||
各位大牛,所有变态数据我都过了就还是WA,谁帮我看看,先排序后DP的#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator