状态转移
状态转移之前先讲讲双指针,因为看题目之前第一眼觉得是双指针
这道题不能用它去做,因为题目没说要序列一定连续,连续不能满足,二段性也就不用考虑
状态转移的思路比较简单
设f[i]
代表前i个数中最长上升子序列的长度
f[i] = max(f[j] + 1, f[i]) (1 <= j < i && a[j] < a[i)
时间复杂度 O(n ^ 2)
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, res;
int f[N], a[N];
inline void solve()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = 1; i <= n; i ++ )
{
f[i] = 1;
for (int j = 1; j < i; j ++ )
if (a[j] < a[i] && f[i] < f[j] + 1)
f[i] = f[j] + 1;
if (res < f[i]) res = f[i];
}
cout << res << endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
solve();
return 0;
}
优化(贪心 + 二分)
二分:
第一种:[l , mid] [mid+1, r]
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
求解最大值的最小值 Min(>=x)
第二种:[l , mid-1] [mid , r]
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
求解最小值的最大值 Max(<=x)
注:这里的>=x只是我们定义的check( )
来源:https://www.acwing.com/blog/content/91/
我们总是求出在当前状态下长度为i的非降序列的末尾元素的最小值,这样,后面的元素就有最大的概率加入到非降序列中,最后求出最长非降子序列的长度
设f[i] 表示长度为i的解序列的末尾元素的最小值
1.当a[i]大于等于f的尾部元素时,直接将其加到f的尾部
2.当a[i]小于f尾部元素时,在b中找到a[i]处于哪两个元素之间,然后将较大的那个替换为a[i]
时间复杂度 O(nlogn)
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, res = 1;
int f[N], a[N];
inline void solve()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
f[1] = a[1];
for (int i = 2; i <= n; i ++ )
{
if (a[i] > f[res]) f[ ++res] = a[i];
else
{
int l = 1, r = res;
while(l < r)
{
int mid = (l + r) >> 1;
if (f[mid] < a[i]) l = mid + 1;
else r = mid;
}
f[r] = a[i];
}
}
cout << res << endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
solve();
return 0;
}
//y总的简洁代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, res;
int f[N], a[N];
inline void solve()
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> a[i];
for (int i = 0; i < n; i ++ )
{
int l = 0, r = res;
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (f[mid] < a[i]) l = mid;
else r = mid - 1;
}
if (res < r + 1) res = r + 1;
f[r + 1] = a[i];
}
cout << res << endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
solve();
return 0;
}