PAT L2-014 列车调度（Dilworth定理）

分析

比赛的时候一直在贪心做来着，一直WA。 卧槽，原来是一个定理啊。 Dilworth定理 还不懂的戳这里； 总之就是一句话，最长反链长==偏序链的划分数、 这里的偏序链为递减的，那就是要求 最长递增子序列的长度了； 再一看数据范围挺大的，得用nlogn的那种解法了：

AC代码：

#include <iostream> #include <cmath> #include <cstring> typedef long long ll; typedef unsigned long long ull; using namespace std; const int maxn = 1e5 + 100; const int inf = 999999999; int dp[maxn], a[maxn]; int main() { #ifdef LOCAL //freopen("L2-014(Dilworth).in","r",stdin); //freopen("L2-014(Dilworth).out","w",stdout); #endif int n; while(cin >> n) { int len = 0; memset(dp, 0, sizeof(dp)); for(int i = 0; i < n; i++) { int x; cin >> x; if(len == 0 || x >= dp[len-1]) dp[len++] = x; else { int l = 0, r = len - 1; while(l <= r) { int mid = (l+r)/2; if(dp[mid] <= x) l = mid+1; else r = mid - 1; } dp[l] = min(dp[l], x); } } cout << len << endl; } return 0; }