也会有发光的一天吖

用户名：wzi

访问量：8657

签　名：

我怎么能这么笨啊，脑袋长的干嘛的？

等　　级
排　　名	113
经　　验	7940
参赛次数	0
文章发表	37
年　　龄	88
在职情况	学生
学　　校	蓝翔技校
专　　业

　　自我简介：

1.素质教育漏网之鱼 2.晚睡协会常任理事3.情侣辩论赛冠军 4. 国家级抬杠运动员6.中国驰名窝里横 7.家里蹲大学博士

TA的其他文章

Java语言编写的
浏览：118

学生信息管理系统
浏览：242

最通熟易懂的表达
浏览：35

你可能喜欢

A+B for Input-Output Practice (VI) （C语言代码）

蓝桥杯2022年第十三届省赛真题-最长不下降子序列

　　作者: 也会有发光的一天吖　　　　发表时间：2023-04-05 20:28:53 浏览：644　|　评论：0　

原题链接：蓝桥杯2022年第十三届省赛真题-最长不下降子序列

```c
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define debug(x) cout<<"target is "<<x<<endl
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define all(a) a.begin(),a.end()
#define oper(a) (operator<(const a& ee)const)
#define endl "\n"
#define ul (u << 1)
#define ur (u << 1 | 1)
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

const int N = 200010, M = 500010, MM = 110;
int INF = 0x3f3f3f3f, mod = 998244353;
ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, k;
int z[N], dpl[N], dpr[N];
vector<int> vec;
int find(int x) { //离散化排序后二分查找元素位置
    return lower_bound(all(vec), x) - vec.begin() + 1;
}

struct tree
{
    int l, r, mx;
}tr[N << 2];
inline void pushup(int u) {
    tr[u].mx = max(tr[ul].mx, tr[ur].mx);//维护max
}
void build(int u, int l, int r) {
    if (l == r)tr[u] = { l,r,0 };
    else {
        tr[u] = { l,r,0 };
        int mid = l + r >> 1;
        build(ul, l, mid), build(ur, mid + 1, r);
    }
}
void modify(int u, int d, int f) {
    if (tr[u].l == d && tr[u].r == d) {
        tr[u].mx = f;
    }
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (mid >= d)modify(ul, d, f);
        if (mid < d)modify(ur, d, f);
        pushup(u);
    }
}
int query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) {
        return tr[u].mx;
    }
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        int t = 0;
        if (mid >= l)t = query(ul, l, r);
        if (mid < r)t = max(t, query(ur, l, r));
        return t;
    }
}

void solve() {
    cin >> n >> k;
    forr(i, 1, n)cin >> z[i], vec.push_back(z[i]);
    sort(all(vec));
    vec.erase(unique(all(vec)), vec.end());

m = vec.size();
    build(1, 1, m);

int ans = k;

//先用这个思想维护出从左到右 i 位置的最长不下降子序列
    forr(i, 1, n) {
        int t = find(z[i]);
        int res = query(1, 1, t) + 1;
        //从小于等于z[i]的区间中找 max(dpl值)

dpl[i] = res;
        ans = max(ans, dpl[i]);

modify(1, t, res);
        //同时更新此位置，维护此位置 max(dpl值)
    }

build(1, 1, m);

//同样维护从右到左 i 位置的最长不上升子序列
    for (int i = n; i; i--) {
        int t = find(z[i]);
        int res = query(1, t, m) + 1;
        dpr[i] = res;
        ans = max(ans, dpr[i]);
        modify(1, t, res);

//但这里维护的同时要随时与 k 个前的 dpl[be] 取 max
        int be = i - k - 1;
        if (be >= 1) {
            int tt = find(z[be]);
            ans = max(ans, dpl[be] + k + query(1, tt, m));
            //维护到此位置的权值线段树中，在比 z[be] 大的区间中找 max 值

//这样才能保证没有遗漏，因为中间可能不止空出 k 个数
        }
    }

//最后还有记录不连接两区间，直接加 k 的情况
    for (int i = 1; i + k <= n; i++)
        ans = max(ans, dpl[i] + k);
    for (int i = n; i - k >= 1; i--)
        ans = max(ans, dpr[i] + k);

cout << ans;
}

int main() {
    cinios;
    int T = 1;
    forr(t, 1, T) {
        solve();
    }
    return 0;
}
/*
8 2
5 6 100 99 98 97 7 8

//答案是 6
*/

```

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

也会有发光的一天吖

TA的其他文章

你可能喜欢

用筛法求之N内的素数。（C语言代码）

A+B for Input-Output Practice (VI) （C语言代码）

C二级辅导-求偶数和（C语言代码）

C二级辅导-进制转换（C语言代码）

C二级辅导-计负均正（C语言代码）

蓝桥杯2022年第十三届省赛真题-最长不下降子序列

评论区

精彩推荐

求最大公约数-模板题

三进制小数（C语言代码）

点我有惊喜！你懂得！

C语言训练-斐波纳契数列（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

【绝对值排序】（C++代码）

字符串比较（C语言代码）答案错误？？？？

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

模拟计算器（C++代码）

也会有发光的一天吖

TA的其他文章

你可能喜欢

用筛法求之N内的素数。 （C语言代码）

A+B for Input-Output Practice (VI) （C语言代码）

C二级辅导-求偶数和 （C语言代码）

C二级辅导-进制转换 （C语言代码）

C二级辅导-计负均正 （C语言代码）

蓝桥杯2022年第十三届省赛真题-最长不下降子序列

评论区

精彩推荐

求最大公约数-模板题

三进制小数 （C语言代码）

点我有惊喜！你懂得！

C语言训练-斐波纳契数列 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

【绝对值排序】 （C++代码）

字符串比较 （C语言代码）答案错误？？？？

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

模拟计算器 （C++代码）

用筛法求之N内的素数。（C语言代码）

C二级辅导-求偶数和（C语言代码）

C二级辅导-进制转换（C语言代码）

C二级辅导-计负均正（C语言代码）

　　评论区

三进制小数（C语言代码）

C语言训练-斐波纳契数列（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

【绝对值排序】（C++代码）

字符串比较（C语言代码）答案错误？？？？

模拟计算器（C++代码）