avatar
fireworks99
keep hungry keep foolish

POJ 2533 Longest Ordered Subsequence

Description

最长上升子序列(模板)

O(n * n)

#include <cstdio> #include <iostream> #include <algorithm> using namespace std; int a[10005]; int dp[10005]; int main() { int n; while(~scanf("%d", &n)) { for(int i = 0; i < n; ++i) scanf("%d", &a[i]); int ans = 0; for(int i = 0; i < n; ++i) { dp[i] = 1; for(int j = 0; j < i; ++j) { if(a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1); } ans = max(ans, dp[i]); } cout << ans << '\n'; } return 0; }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

O(n * logn) 不能记录路径

#include <cstdio> #include <iostream> #include <algorithm> using namespace std; const int INF = 0x3f3f3f3f; int a[10005]; int low[10005]; int main() { int n; while(~scanf("%d", &n)) { ///这个算法里数组尽量从1开始存 for(int i = 1; i <= n; ++i) { scanf("%d", &a[i]); low[i] = INF; } int ans = 1; low[ans] = a[1]; for(int i = 2; i <= n; ++i) { if(a[i] > low[ans]) low[++ans] = a[i]; else { int pos = lower_bound(low, low + ans, a[i]) - low; low[pos] = a[i]; } } cout << ans << '\n'; } return 0; }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
Site by Baole Zhao | Powered by Hexo | theme PreciousJoy