最长上升子序列(LIS)的三种求法 dp

之前写LIS，只知道两种，一种最基础的n2，一种是n * log(n)的二分。
这两个应该人尽皆知。
但是如果权值如果不为1， n又非常大，则n2和二分都没法用了，
但是可以使用树状数组来维护（貌似也是人尽皆知），这种做法的思想跟第一种n2很像，大的值，可以由前面小
的值转移，这个时候使用树状数组维护，将原来的修改，求和改为最大值更新和获取即可。
具体含义即c[x]表示最大值≤x的最长子序列长度，当前添加的数字为x，则查询c[x - 1]即
最大值小于等于x-1的最长上升子序列，假设求得长度是y，则最大值大于等于x的最长上升子序列的长度都跟y + 1更新一次。
下面是三种LIS的求法
一
直接暴力求，从后往前扫(复杂度O(n2))

#include #include using namespace std; #define sz(a) ((int)(a).size()) typedef long long ll; bool cmp(int a, int b) { return a > b; } #define me(a, b) (memset(a, b, sizeof a)) const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; const double PI = acos(-1); const int N = 2e5 + 10; #define bo bool operator < (const node &oth)constint a[N]; int b[N]; int main() { int n; while (cin >> n) { memset(b, 0, sizeof b); int ans = 0; for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= n; i++) { b[i] = 1; for (int j = 1; j < i; j++) { if (a[i] > a[j])// 若为非严格递增，则改为>= b[i] = max(b[i], b[j] + 1); } ans = max(ans, b[i]); } cout << ans << endl; } return 0; }

二
使用二分优化，每次选取最有潜力的上升子序列，复杂度(O(n * log(n)))

#include #include using namespace std; #define sz(a) ((int)(a).size()) typedef long long ll; bool cmp(int a, int b) { return a > b; } #define me(a, b) (memset(a, b, sizeof a)) const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; const double PI = acos(-1); const int N = 2e5 + 10; #define bo bool operator < (const node &oth)constint a[N]; int d[N]; int main() { int n; while (cin >> n) { memset(d, 0x3f, sizeof d); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= n; i++) { int j = lower_bound(d + 1, d + n + 1, a[i]) - d; //若为非严格递增，则改为upper_bound d[j] = a[i]; } int len = lower_bound(d + 1, d + n + 1, 0x3f3f3f3f) - d - 1; cout << len << endl; } return 0; }

【最长上升子序列(LIS)的三种求法】三
使用树状数组维护前缀最大值，每次查询并更新前缀区间最大值。

#include #include using namespace std; #define sz(a) ((int)(a).size()) typedef long long ll; bool cmp(int a, int b) { return a > b; } #define me(a, b) (memset(a, b, sizeof a)) const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; const double PI = acos(-1); const int N = 2e5 + 10; #define bo bool operator < (const node &oth)constll a[N]; ll c[N]; vectorv; inline ll lowbit(ll x) { return x & -x; } void add(ll x, ll y, ll n) { while (x <= n) { c[x] = max(c[x], y); x += lowbit(x); } } ll ask(ll x) { ll res = 0; while (x) { res = max(res, c[x]); x -= lowbit(x); } return res; } int main(){ ll n; while (cin >> n) { v.clear(); me(c, 0); for (ll i = 1; i <= n; i++) cin >> a[i], v.push_back(a[i]); sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); ll ans = 0; for (ll i = 1; i <= n; i++) { ll x = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1; ll y = ask(x - 1); // 若为非严格递增，则改为查x ans = max(ans, y + 1); add(x, y + 1, n); } cout << ans << endl; } return 0; }

掌握了第三种可以去做下这题。
https://ac.nowcoder.com/acm/contest/992/B

#include using namespace std; #define sz(a) ((int)(a).size()) typedef long long ll; #define me(a, b) (memset(a, b, sizeof a)) const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; const double PI = acos(-1); const int N = 2e5 + 10; ll a[N]; ll c[N]; vectorv; inline ll lowbit(ll x) { return x & -x; } void add(ll x, ll y, ll n) { while (x <= n) { c[x] = max(c[x], y); x += lowbit(x); } } ll ask(ll x) { ll res = 0; while (x) { res = max(res, c[x]); x -= lowbit(x); } return res; } int main(){ ll n; cin >> n; for (ll i = 1; i <= n; i++) cin >> a[i], v.push_back(a[i]); sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); ll ans = 0; ll num; for (ll i = 1; i <= n; i++) { cin >> num; ll x = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1; ll y = ask(x); ans = max(ans, num + y); add(x, num + y, n); } cout << ans << endl; return 0; }