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 |
贴代码// 类似于最长上升子序列 #include <stdio.h> #include <string.h> const int maxN = 30006; int data[maxN]; int rank[maxN]; int n; void inputData() { scanf("%d", &n); for (int i = 0; i < n; ++ i) { scanf("%d", &data[i]); } } void process() { memset(rank, 0, sizeof(rank)); rank[0] = 0; rank[1] = data[0]; int rLen = 2; for (int i = 1; i < n; ++ i) { for (int j = rLen - 1; j >= 0; -- j) { if (j & 1) { if (rank[j] > data[i]) { if (j == rLen - 1) { rank[rLen] = data[i]; ++ rLen; } else if (rank[j + 1] > data[i]) { rank[j + 1] = data[i]; } break; } } else { if (rank[j] < data[i]) { if (j == rLen - 1) { rank[rLen] = data[i]; ++ rLen; } else if (rank[j + 1] < data[i]) { rank[j + 1] = data[i]; } break; } } } } printf("%d\n", rLen - 1); } int main() { int cases; scanf("%d", &cases); for (int i = 0; i < cases; ++ i) { inputData(); process(); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator