avatar
文章
215
标签
3
分类
3
主页
分类
标签
归档
友链
爱飞鱼的blog决策单调性优化dp
搜索
主页
分类
标签
归档
友链

决策单调性优化dp

发表于2024-07-07|更新于2025-08-05|ICPC
|浏览量:

title: 决策单调性优化dp
categories:

  • ICPC
    tags:
  • null
    abbrlink: 67361f08
    date: 2024-07-07 00:00:00

决策单调性优化dp学习笔记

决策单调性优化dp学习笔记 - birchtree - 博客园 (cnblogs.com)

文章作者: WTY
文章链接: https://my-mathmaster-github-io.vercel.app/posts/67361f08.html
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 爱飞鱼的blog！
cover of previous post
上一篇
普通对顶堆
title: 普通对顶堆 categories: ICPC tags: null abbrlink: d860667d date: 2024-06-27 00:00:00 动态维护第k大 priority_queue<int> a; //大根堆 priority_queue<int,vector<int>,greater<int> > b; for(int i=1; i<=n; i++){ int x; scanf("%d",&x); if(b.empty()||x>=b.top()) b.push(x); //插入 else a.push(x); int k=max(1,i*w/100); //第k大 while(b.size()>k) a.push(b.top()), b.pop(); //调整 while(b.size()<k) b.push(a.top()),...
cover of next post
下一篇
质因数分解
title: 质因数分解 categories: ICPC tags: null abbrlink: e7d92776 date: 2024-07-09 00:00:00 acwing的最基础模板 https://www.acwing.com/blog/content/406/ 知乎大佬给的各种数据范围模板大全：https://zhuanlan.zhihu.com/p/591377294 对于其中的一部分进行提炼形成自己的模板 1.使用场景：假设有n个数需要分解，每个数最大可能是N,下面给出的这种代码的时间复杂度是O(nlogN)O(nlogN)O(nlogN) 思想：通过O(n)O(n)O(n)线性筛预处理过程中记录范围内每个数的最小质因数，分解时每个数的最多被计算O(logN)O(logN)O(logN)次。 //预处理： for (int i = 2; i < N; i++)minp[i] = i;//通过这个初始化省下bool数组空间 int cnt = 0; for (int i = 2; i < N; i++) { if...
avatar
WTY
理性思考，和平交流
文章
215
标签
3
分类
3
Follow Me
目录
  1. 1. 决策单调性优化dp学习笔记
最新文章
贪心
贪心2024-12-22
Z函数与扩展KMP算法详解 - 以CF126B为例
Z函数与扩展KMP算法详解 - 以CF126B为例2024-12-21
Codeforces Round 895 (Div. 3)
Codeforces Round 895 (Div. 3)2024-12-16
可持久化字典树（Trie）
可持久化字典树（Trie）2024-12-16
网格图上问题
网格图上问题2024-12-15
©2022 - 2025 By WTY
框架 Hexo|主题 Butterfly
Copyright 爱飞鱼
搜索
数据加载中