单调队列优化DP问题

目录

1.滑动窗口

2.最大子序和

3.旅行问题

4.烽火传递

5.绿色通道

6.修剪草坪

7.理想的正方形

1.滑动窗口

154.给定一个大小为 n≤106 的数组。

有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。

你只能在窗口中看到 k 个数字。

每次滑动窗口向右移动一个位置。

以下是一个例子：

该数组为 [1 3 -1 -3 5 3 6 7]，k 为 33。

窗口位置最小值最大值
[1 3 -1] -3 5 3 6 7-13
1 [3 -1 -3] 5 3 6 7-33
1 3 [-1 -3 5] 3 6 7-35
1 3 -1 [-3 5 3] 6 7-35
1 3 -1 -3 [5 3 6] 736
1 3 -1 -3 5 [3 6 7]37

你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

输入格式

输入包含两行。

第一行包含两个整数 n 和 k，分别代表数组长度和滑动窗口的长度。

第二行有 n 个整数，代表数组的具体数值。

同行数据之间用空格隔开。

#include<iostream>
#include<algorithm>
​
using namespace std;
​
const int N = 1000010;
​
int n, k;
int a[N], q[N];
​
int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 0;i < n; i++)
        scanf("%d", &a[i]);
    
    int tt = -1, hh = 0;
    for(int i = 0;i < n; i++)
    {
        if(hh <= tt && q[hh] < i - k + 1) hh++;
        while(hh <= tt && a[q[tt]] >= a[i]) tt--;
        
        q[++tt] = i;
        if(i >= k - 1) printf("%d ", a[q[hh]]);
    }
    puts("");
    
    tt = -1, hh = 0;
    for(int i = 0;i < n; i++)
    {
        if(hh <= tt && q[hh] < i - k + 1) hh++;
        while(hh <= tt && a[q[tt]] <= a[i]) tt--;
        
        q[++tt] = i;
        if(i >= k - 1) printf("%d ", a[q[hh]]);
    }
    puts("");
    
    return 0;
}

2.最大子序和

输入一个长度为 n 的整数序列，从中找出一段长度不超过 m 的连续子序列，使得子序列中所有数的和最大。

注意： 子序列的长度至少是 1。

输入格式

第一行输入两个整数 n,m。

第二行输入 n 个数，代表长度为 n 的整数序列。

同一行数之间用空格隔开。

闫氏最优化问题分析法

在一个有限集合中求最值，或者求个数。

#include<iostream>
#include<algorithm>
#include<cstring>
​
using namespace std;
​
const int N = 300010;
​
int n, m;
int s[N], q[N];
​
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1;i <= n; i++)
    {
        scanf("%d", &s[i]);
        s[i] += s[i - 1];
    }
    
    int res = 0;
    for(int i = 1;i <= n; i++)
    {
        res = min(res, s[i] - s[i - 1]);
    }
    
    int hh = 0, tt = 0;
    for(int i = 1;i <= n; i++)
    {
        if(q[hh] < i - m) hh++;
        res = max(res, s[i] - s[q[hh]]);
        while(hh <= tt && s[q[tt]] >= s[i]) tt--;
        q[++tt] = i;
    }
    
    printf("%d\n", res);
    
    return 0;
}

3.旅行问题

1088.John 打算驾驶一辆汽车周游一个环形公路。

公路上总共有 n 个车站，每站都有若干升汽油（有的站可能油量为零），每升油可以让汽车行驶一千米。

John 必须从某个车站出发，一直按顺时针（或逆时针）方向走遍所有的车站，并回到起点。

在一开始的时候，汽车内油量为零，John 每到一个车站就把该站所有的油都带上（起点站亦是如此），行驶过程中不能出现没有油的情况。

任务：判断以每个车站为起点能否按条件成功周游一周。

输入格式 第一行是一个整数 n，表示环形公路上的车站数；

接下来 n 行，每行两个整数 pi,di，分别表示表示第 i 号车站的存油量和第 i 号车站到 顺时针方向 下一站的距离。

#include<iostream>
#include<algorithm>
#include<cstring>
​
using namespace std;
​
const int N = 1e6 + 10;
​
typedef long long LL;
​
int n;
int p[N], d[N];
LL s[N];
int q[N];
bool st[N];
​
int main()
{
    scanf("%d", &n);
    for(int i = 1;i <= n; i++)
        scanf("%d%d", &o[i], &d[i]);
    
    //顺时针链
    for(int i = 1;i <= n; i++)
        s[i] = s[i + 1] = o[i] - d[i];
    for(int i = 1;i <= n * 2; i++)
        s[i] += s[i - 1];
    
    int hh = 0, tt = -1;
    for(int i = n * 2;i >= 1; i--)
    {
        if(hh <= tt && q[hh] > i + n) hh++;
        while(hh <= tt && s[q[tt]] >= s[i]) tt--;
        q[++tt] = i;
        if(i <= n) 
        {
            if(s[q[hh]] >= s[i - 1])
                st[i] = true;
        }
    }
    
    //逆时针链
    d[0] = d[n];
    for(int i = 1;i <= n; i++)
        s[i] = s[i + 1] = o[i] - d[i - 1];
    for(int i = 1;i <= 2 * n; i++)
        s[i] += s[i - 1];
    
    hh = 0, tt = -1;
    for(int i = 1;i <= 2 * n; i++)
    {
        if(hh <= tt && q[hh] < i - n) hh++;
        if(i > n)
        {
            if(s[q[hh]] <= s[i])
                st[i - n] = true;
        }
        while(hh <= tt && s[q[tt]] <= s[i]) tt--;
        q[++tt] = i;
    }
    
    for(int i = 1;i <= n; i++)
        if(st[i]) puts("TAK");
        else puts("NIE");
    
    return 0;
}

4.烽火传递

烽火台是重要的军事防御设施，一般建在交通要道或险要处。

一旦有军情发生，则白天用浓烟，晚上有火光传递军情。

在某两个城市之间有 n 座烽火台，每个烽火台发出信号都有一定的代价。

为了使情报准确传递，在连续 m 个烽火台中至少要有一个发出信号。

现在输入 n,m 和每个烽火台的代价，请计算在两城市之间准确传递情报所需花费的总代价最少为多少。

输入格式 第一行是两个整数 n,m，具体含义见题目描述；

第二行 n 个整数表示每个烽火台的代价 ai。

在这里插入图片描述

#include<iostream>
#include<algorithm>
#include<cstring>
​
using namespace std;
​
const int N = 200010;
​
int n, m;
int w[N];
int f[N];
int q[N];
​
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1;i <= n; i++) scanf("%d", &w[i]);
    
    int hh = 0, tt = 0;
    for(int i = 1;i <= n; i++)
    {
        if(q[hh] < i - m) hh++;
        f[i] = f[q[hh]] + w[i];
        while(hh <= tt && f[q[tt]] >= f[i]) tt--;
        q[++tt] = i;
    }
    
    int res = 1e9;
    for(int i = n - m + 1;i <= n; i++)
        res = min(res, f[i]);
    
    return 0;
}

详细学习：模拟队列

5.绿色通道

高二数学《绿色通道》总共有 n 道题目要抄，编号 1,2,…,n，抄第 i 题要花 ai 分钟。

小 Y 决定只用不超过 t 分钟抄这个，因此必然有空着的题。

每道题要么不写，要么抄完，不能写一半。

下标连续的一些空题称为一个空题段，它的长度就是所包含的题目数。

这样应付自然会引起马老师的愤怒，最长的空题段越长，马老师越生气。

现在，小 Y 想知道他在这 t 分钟内写哪些题，才能够尽量减轻马老师的怒火。

由于小 Y 很聪明，你只要告诉他最长的空题段至少有多长就可以了，不需输出方案。

输入格式

第一行为两个整数 n，t。

第二行为 n 个整数，依次为 a1,a2,…,an。

#include<iostream>
#include<algorithm>
#include<cstring>
​
using namespace std;
​
const int N = 50010;
​
int n, m;
int q[N], f[N];
int w[N];
​
bool check(int limit)
{
    int hh = 0, tt = 0;
    for(int i = 1;i <= n; i++)
    {
        if(q[hh] < i - limit - 1) hh++;
        f[i] = f[q[hh]] + w[i];
        while(hh <= tt && f[q[tt]] >= f[i]) tt--;
        q[++tt] = i;
    }
    
    for(int i = n - limit;i <= n; i++)
        if(f[i] <= m)
            return true;
    
    return false;
}
    
​
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1;i <= n; i++)
        scanf("%d", &w[i]);
    
    int l = 0, r = n;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    
    printf("%d\n", r);
    return 0;
}

6.修剪草坪

1087.在一年前赢得了小镇的最佳草坪比赛后，FJ变得很懒，再也没有修剪过草坪。 现在，新一轮的最佳草坪比赛又开始了，FJ希望能够再次夺冠。 然而，FJ的草坪非常脏乱，因此，FJ只能够让他的奶牛来完成这项工作。 FJ有N只排成一排的奶牛，编号为1到N。 每只奶牛的效率是不同的，奶牛i的效率为。 编号相邻的奶牛们很熟悉，如果FJ安排超过K只编号连续的奶牛，那么这些奶牛就会罢工去开派对。 因此，现在FJ需要你的帮助，找到最合理的安排方案并计算FJ可以得到的最大效率。 注意，方案需满足不能包含超过K只编号连续的奶牛。

#include<iostream>
#include<algorithm>
#include<cstring>
​
using namespace std;
​
typedef long long LL;
​
const int N = 100010;
​
int n, m;
LL s[N];
LL f[N];
int q[N];
​
LL g(int i)
{
    return f[i - 1] - s[i];
}
​
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1;i <= n; i++)
    {
        scanf("%lld", &s[i]);
        s[i] += s[i - 1];
    }
    
    int hh = 0, tt = 0;
    for(int i = 1;i <= n; i++)
    {
        if(q[hh] < i - m) hh++;
        f[i] = max(f[i - 1], g(q[hh]) + s[i]);
        while(hh <= tt && g(q[tt]) <= g[i]) tt--;
        q[++tt] = i;
    }
    
    printf("%lld\n", f[n]);
    return 0;
}

440.道路问题（非常复杂）

7.理想的正方形

有一个a x b的整数组成的矩阵，现请你从中找出一个n x n的正方形区域，使得该区域所有数中的最大值和最小值之差最小。

#include<iostream>
#include<algorithm>
#include<cstring>
​
using namespace std;
​
const int N = 1010;
​
int n, m, k;
int w[N][N];
int row_max[N][N], col_max[N][N];
​
void get_min(int a[], int b[], int tot)
{
    int hh = 0, tt = -1;
    for(int i = 1;i <= tot; i++)
    {
        if(hh <= tt && q[hh] <= i - k) hh++;
        while(hh <= tt && a[q[tt]] >= a[i]) tt--;
        q[++tt] = i;
        b[i] = a[q[hh]];
    }
}
​
void get_max(int a[], int b[], int tot)
{
    int hh = 0, tt = -1;
    for(int i = 1;i <= tot; i++)
    {
        if(hh <= tt && q[hh] <= i - k) hh++;
        while(hh <= tt && a[q[tt]] <= a[i]) tt--;
        q[++tt] = i;
        b[i] = a[q[hh]];
    }
}
​
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= m; j++)
            scanf("%d", &w[i][j]);
    
    for(int i = 1;i <= n; i++)
    {
        get_min(w[i], row_min[i], m);
        get_max(w[i], row_max[i], m);
    }
    
    int res = 1e9;
    int a[N], b[N], c[N];
    for(int i = k;i <= m; i++)
    {
        for(int j = 1;j <= n; j++) a[j] = row_min[j][i];
        get_min(a, b, n);
        
        for(int j = 1;j <= n; j++) a[j] = row_max[j][i];
        get_max(a, c, n);
        
        for(int j = k;j <= n; j++) res -= min(res, c[j] - b[j]);
    }
    
    printf("%d\n", res);
    
    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/385596.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

力扣_面试题：配对交换

力扣_面试题：配对交换

配对交换 链接&#xff1a;力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 题目意思就是交换相邻两个二进制位 &#xff0c;用&分别取出even&#xff08;偶位和&#xff09;odd&#xff08;奇位和&#xff09; 偶位和用0xAAAAAAAA&#xff0c;奇…
阅读更多...
ONLYOFFICE桌面编辑器8.0新特性：PDF表单、RTL支持、Moodle集成、本地界面主题等

ONLYOFFICE桌面编辑器8.0新特性：PDF表单、RTL支持、Moodle集成、本地界面主题等

ONLYOFFICE是由领先的IT公司—Ascensio System SIA经验丰富的IT专家开发的项目。这是一款强大的在线编辑器&#xff0c;能够为提供高效的文本文档、电子表格、演示文稿、表单和 PDF 编辑工具。 继 ONLYOFFICE 文档 v8.0发布后&#xff0c;适用于 Linux、Windows 和 macOS 的免费…
阅读更多...
【C语言】实现栈

【C语言】实现栈

目录 &#xff08;一&#xff09;栈 &#xff08;二&#xff09;头文件 &#xff08;三&#xff09;功能实现 &#xff08;1&#xff09;初始化栈 &#xff08;2&#xff09; 栈的销毁 &#xff08;3&#xff09;压栈 &#xff08;4&#xff09; 出栈 &#xff08;5&a…
阅读更多...
MATLAB知识点：unifrnd函数（★★★☆☆）生成任意区间内均匀分布的随机数

MATLAB知识点：unifrnd函数（★★★☆☆）生成任意区间内均匀分布的随机数

​讲解视频&#xff1a;可以在bilibili搜索《MATLAB教程新手入门篇——数学建模清风主讲》。​ MATLAB教程新手入门篇&#xff08;数学建模清风主讲&#xff0c;适合零基础同学观看&#xff09;_哔哩哔哩_bilibili 节选自第3章&#xff1a;课后习题讲解中拓展的函数 在讲解第…
阅读更多...
Vue3高频知识点和写法

Vue3高频知识点和写法

一 Vue插件 二 vue3项目创建 创建完成后npm install npm run dev 三 setup 一 响应式数据 setup函数是用来代替data和methods的写法的&#xff0c;在setup函数中声明的数据和函数&#xff0c;导出后可以在页面中使用。 但是暂时不是响应式数据&#xff0c;如果要响应式数据的…
阅读更多...
2023年03月CCF-GESP编程能力等级认证C++编程二级真题解析

2023年03月CCF-GESP编程能力等级认证C++编程二级真题解析

一、单选题（每题2分，共30分） 第1题 以下存储器中的数据不会受到附近强磁场干扰的是（ ）。 A．硬盘 B．U盘 C．内存 D．光盘 答案：D 第2题 下列流程图，属于计算机的哪种程序结构？（ ）。 A．顺序结构 B．循环结构 C．分支结构 D．数据结构 答案：C 第3题 下列关…
阅读更多...
CVE-2023-22602 漏洞复现

CVE-2023-22602 漏洞复现

CVE-2023-22602 简述&#xff1a; 由于 1.11.0 及之前版本的 Shiro 只兼容 Spring 的ant-style路径匹配模式&#xff08;pattern matching&#xff09;&#xff0c;且 2.6 及之后版本的 Spring Boot 将 Spring MVC 处理请求的路径匹配模式从AntPathMatcher更改为了PathPatter…
阅读更多...
【数据结构】11 堆栈（顺序存储和链式存储）

【数据结构】11 堆栈（顺序存储和链式存储）

定义 可认为是具有一定约束的线性表&#xff0c;插入和删除操作都在一个称为栈顶的端点位置。也叫后入先出表&#xff08;LIFO&#xff09; 类型名称&#xff1a;堆栈&#xff08;STACK&#xff09; 数据对象集&#xff1a; 一个有0个或者多个元素的有穷线性表。 操作集&#…
阅读更多...
【医学知识图谱 自动补全 关系抽取】生成模型 + 医学知识图谱 = 发现三元组隐藏的关系实体对

【医学知识图谱 自动补全 关系抽取】生成模型 + 医学知识图谱 = 发现三元组隐藏的关系实体对

生成模型 医学知识图谱 发现三元组新关系实体对 提出背景问题&#xff1a;如何自动发现并生成医疗领域中未被标注的实体关系三元组&#xff1f;CRVAE模型 提出背景 论文&#xff1a;https://dl.acm.org/doi/pdf/10.1145/3219819.3220010 以条件关系变分自编码器&#xff08;…
阅读更多...
【51单片机】定时器（江科大）

【51单片机】定时器（江科大）

7.1定时器 1.定时器介绍: 51单片机的定时器属于单片机的内部资源,其电路的连接和运转均在单片机内部完成 2. 定时器作用: (1)用于计时系统,可实现软件计时,或者使程序每隔一固定时间完成一项操作 (2)替代长时间的Delay,提高CPU的运行效率和处理速度 定时器在单片机内部就像一个…
阅读更多...
模型 “焦糖布丁”理论

模型 “焦糖布丁”理论

系列文章 主要是 分享 思维模型&#xff0c;涉及各个领域&#xff0c;重在提升认知。关注需求本质。 1 “焦糖布丁”理论的应用 1.1 “焦糖布丁”理论-海底捞的创新 海底捞以其优质的服务而闻名&#xff0c;它的成功之处在于深刻理解了消费者的需求和任务&#xff0c;并提供了…
阅读更多...
【运维测试】测试理论+工具总结笔记第1篇：测试理论的主要内容（已分享，附代码）

【运维测试】测试理论+工具总结笔记第1篇：测试理论的主要内容（已分享，附代码）

本系列文章md笔记&#xff08;已分享&#xff09;主要讨论测试理论测试工具相关知识。Python测试理论的主要内容&#xff0c;掌握软件测试的基本流程&#xff0c;知道软件测试的V和W模型的优缺点&#xff0c;掌握测试用例设计的要素&#xff0c;掌握等价类划分法、边界值法、因…
阅读更多...
React18原理: 时间分片技术选择

React18原理: 时间分片技术选择

渲染1w个节点的不同方式 1 &#xff09;案例1&#xff1a;一次渲染1w个节点 <div idroot><div><script type"text/javascript">function randomHexColor() {return "#" ("0000" (Math.random() * 0x1000000 << 0).toS…
阅读更多...
【51单片机】蜂鸣器（江科大）

【51单片机】蜂鸣器（江科大）

11.1蜂鸣器 1.蜂鸣器介绍 蜂鸣器是一种将电信号转换为声音信号的器件,常用来产生设备的按键音、报警音等提示信号 蜂鸣器按驱动方式可分为有源蜂鸣器和无源蜂鸣器 有源蜂鸣器:内部自带振荡源,将正负极接上直流电压即可持续发声,频率固定 无源蜂鸣器:内部不带振荡源,需…
阅读更多...
【MATLAB】小波神经网络回归预测算法

【MATLAB】小波神经网络回归预测算法

有意向获取代码&#xff0c;请转文末观看代码获取方式~也可转原文链接获取~ 1 基本定义 小波神经网络回归预测算法是一种利用小波变换和人工神经网络相结合的方法&#xff0c;用于解决回归预测问题。下面将详细介绍该算法的原理与方法&#xff1a; 小波变换&#xff1a; 小波变…
阅读更多...
Codeforces Round 924 (Div. 2)

Codeforces Round 924 (Div. 2)

Codeforces Round 924 (Div. 2) Codeforces Round 924 (Div. 2) A. Rectangle Cutting 题意&#xff1a;给出a*b的矩形&#xff0c;沿着其中一个边恰好一分为二后可以组成一个新的矩形 思路&#xff1a;判断其中一个边是否可以被2整除以及二分后是否等于另一个边即可 AC cod…
阅读更多...
C++进阶（十六）特殊类设计

C++进阶（十六）特殊类设计

&#x1f4d8;北尘_&#xff1a;个人主页 &#x1f30e;个人专栏:《Linux操作系统》《经典算法试题 》《C》 《数据结构与算法》 ☀️走在路上&#xff0c;不忘来时的初心 文章目录 一、请设计一个类&#xff0c;不能被拷贝二、请设计一个类&#xff0c;只能在堆上创建对象三、…
阅读更多...
腾讯云幻兽帕鲁服务器配置怎么选择合适？

腾讯云幻兽帕鲁服务器配置怎么选择合适？

腾讯云幻兽帕鲁服务器配置怎么选&#xff1f;根据玩家数量选择CPU内存配置&#xff0c;4到8人选择4核16G、10到20人玩家选择8核32G、2到4人选择4核8G、32人选择16核64G配置&#xff0c;腾讯云百科txybk.com来详细说下腾讯云幻兽帕鲁专用服务器CPU内存带宽配置选择方法&#xff…
阅读更多...
8868体育助力西甲最新积分榜 皇马4球大胜稳坐榜一

8868体育助力西甲最新积分榜 皇马4球大胜稳坐榜一

西甲联赛第24轮的四场比赛于2月10日全面收官。其中&#xff0c;皇马在主场迎战吉罗纳队&#xff0c;以4-0的大比分击败对手&#xff0c;将领先优势扩大到5分&#xff0c;稳坐西甲榜首&#xff0c;掌握了争冠的主动权。 威尼修斯的世界波为皇马打开胜利之门&#xff0c;第6分钟就…
阅读更多...
侧信道攻击是什么

侧信道攻击是什么

侧信道攻击是什么? 侧信道攻击是一种利用系统的物理实现或实现的特定属性来获取信息的攻击方式。这些攻击利用了系统在执行特定操作时产生的信息泄漏&#xff0c;而不是直接攻击系统的计算或加密算法。侧信道攻击通常利用系统的功耗、电磁辐射、时间延迟等物理特性进行攻击&a…
阅读更多...
最新文章

Copyright @ 2022~2023