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