树状数组加速dp
由于贪心的LIS解法无法保留每一个位置的最长上升子序列,因此这里给出一种用Fenwick加速的dp方式求LIS,该方法可以保留原来的dp表,利用我们后续使用
时间复杂度: $O(nlogn)$
思路:由于$a_i$的范围很大,考虑做离散化,然后在$a_i$上建立权值树状数组,$tr[i]$表示以不超过 i 结尾的所有最长LIS中长度最大的一个的长度
对于每一个$a_i$,他的最长上升子序列应该是小于 $a_i$的LIS中最长的一个+1
即为 $dp[i] = query(a[i] - 1) + 1$
每次计算出 $dp[i]$ 之后,应该将 $dp[i]$ 更新到Fenwick上去
即 $modify(a[i], ap[i])$
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct Discre
{
vector<int> all;
void insert(int _)
{
all.push_back(_);
}
void insert(vector<int> p)
{
all.insert(all.end(), p.begin(), p.end());
}
void insert(int *p, int len)
{
all.insert(all.end(), p, p + len);
}
Discre(vector<int> p)
{
all = vector<int>(p);
}
Discre(int *p, int len)
{
all = vector<int>(p, p + len);
}
Discre()
{
}
void init()
{
sort(all.begin(), all.end());
all.erase(unique(all.begin(), all.end()), all.end());
}
int index(int p)
{
return lower_bound(all.begin(), all.end(), p) - all.begin();
}
int size()
{
return all.size();
}
int operator[](int idx)
{
return all[idx];
}
};
int tr[N];
void modify(int pos, int x)
{
for (int i = pos; i < N; i += (i & -i))
tr[i] = max(tr[i], x);
}
int query(int R)
{
int res = 0;
for (int i = R; i > 0; i -= (i & -i))
{
res = max(res, tr[i]);
}
return res;
}
int dp[N];
int main()
{
int n;
cin >> n;
vector<int> a(n + 1);
Discre dis;
for (int i = 1; i <= n; i++)
cin >> a[i], dis.insert(a[i]);
dis.init();
for (int i = 1; i <= n; i++)
{
dp[i] = query(dis.index(a[i])) + 1; //这里注意处理一下边界问题
modify(dis.index(a[i] + 1), dp[i]);
}
cout << *max_element(dp + 1,dp + n + 1);
}
另外附上原题中的贪心解法
贪心+二分
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int nums[N];
vector<int> low(N);
int n;
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> nums[i];
low[0]=-2e9;
int len = 0;
for (int i = 1; i <= n; i++)
{
int pos = (lower_bound(low.begin(), low.begin()+len, nums[i]) - low.begin()); //在有序序列中找到第一个可插入位置
len = max(len, pos+1);
low[pos]=nums[i];
}
cout << len;
return 0;
}