1. 2027: [蓝桥杯2022初赛] 最长不下降子序列
传送门:http://oj.ecustacm.cn/problem.php?id=2027
1.1. 题意
给定数组,可以修改连续的个数字变成一个相同值。请计算修改后的最长不下降子序列长度。
1.2. Tag
动态规划、线段树
1.3. 难度
☆☆☆☆☆
1.4. 思路
最长不下降子序列是经典的动态规划问题。本题只和数字大小有关,与数值无关,因此,先对数组进行离散化。
记表示以结尾的最长不下降子序列长度,对于修改连续的个数字变成同一值,最好修改成与前面一样的数字,即:
修改均修改成,此时的最长上升子序列可以看成段:
- :长度为
- :长度为
- :中,以开头的最长上升子序列,注意此时的的值应该等于
为了求出,利用权值线段树求出中最大的数字,同时保证。
具体做法为:对数组离散化后,从左往右遍历数组,将看作线段树的第位,为线段树维护的值(线段树维护最大值),查询线段树区间的最大值即可。
类似的,反向遍历,每次查询的最大值,就可以维护以开头的最长上升子序列,这样,最后暴力枚举每一段即可。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
template <typename T>
inline T read(T& x) {
x = 0;
T w = 1;
char ch = 0;
while (ch < '0' || ch > '9') {
if (ch == '-') w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + (ch - '0');
ch = getchar();
}
return x * w;
}
int a[maxn], b[maxn];
int dp[maxn];
///dp[i]表示以i结尾的最长上升子序列
///权值线段树,维护dp数组
int tree[maxn << 2];
void build(int o, int l, int r)
{
tree[o] = 0;
if(l == r)return;
int mid = (l + r) >> 1;
build(o << 1, l, mid);
build(o << 1 | 1, mid + 1, r);
}
void update(int o, int l, int r, int x, int val)
{
if(l == r)
{
tree[o] = max(tree[o], val);
return;
}
int mid = (l + r) >> 1;
if(x <= mid)update(o << 1, l, mid, x, val);
else update(o << 1 | 1, mid + 1, r, x, val);
tree[o] = max(tree[o << 1], tree[o << 1 | 1]);
}
int query(int o, int l, int r, int L, int R)
{
if(L <= l && r <= R)
return tree[o];
int mid = (l + r) >> 1;
int ans = 0;
if(L <= mid)ans = max(ans, query(o << 1, l, mid, L, R));
if(R > mid)ans = max(ans, query(o << 1 | 1, mid + 1, r, L, R));
return ans;
}
int main()
{
int n, k, tot = 0;
read(n); read(k);
for(int i = 1; i <= n; i++)read(a[i]), b[++tot] = a[i];
if(n == k)
{
cout<<n<<endl;
return 0;
}
///离散化
sort(b + 1, b + 1 + tot);
tot = unique(b + 1, b + 1 + tot) - (b + 1);
for(int i = 1; i <= n; i++)
a[i] = lower_bound(b + 1, b + 1 + tot, a[i]) - b;
build(1, 1, tot);
int ans = 0;
for(int i = 1; i <= n; i++)///从前往后遍历a,放入权值线段树中
{
///dp[i] = max(dp[j]) 满足j=1...i-1 && a[j] <= a[i]
dp[i] = query(1, 1, tot, 1, a[i]) + 1;
update(1, 1, tot, a[i], dp[i]);
}
///重新清空
build(1, 1, tot);
for(int i = n; i > k; i--)///从后往前遍历a,放入权值线段树中
{
///a[i-k+1] ... a[i]相等 均等于a[i-k]
///最后一段要注意:查询的是[a[i-k],tot]中的最大值
ans = max(ans, dp[i - k] + k - 1 + query(1, 1, tot, a[i - k], tot) + 1);
int tmp = query(1, 1, tot, a[i], tot) + 1; ///以a[i]开始的最长上升子序列长度
ans = max(ans, tmp + k);
///插入的是a[i]
update(1, 1, tot, a[i], tmp);
}
cout<<ans<<endl;
return 0;
}