V
主页
【算法进阶】【杂题选讲】【P2034 选择数字】从普通dp入手,带你一步步走向正解,感受做题思考的过程
发布人
求一键五连:点赞、投币、收藏、分享、关注! —————— |复制| —————— #include<bits/stdc++.h> using namespace std;using ll=long long;const ll N=100002; ll n,k,a[N],dp[N],ans=1e18,s;deque<ll> q; int main(){ scanf("%lld%lld",&n,&k); for(ll i=1;i<=n;i++)scanf("%lld",&a[i]),s+=a[i]; q.push_back(0); for(ll i=1;i<=n;i++){ dp[i]=dp[q.front()]+a[i]; while(q.size()&&dp[q.back()]>=dp[i])q.pop_back(); q.push_back(i); while(q.size()&&q.front()<i-k)q.pop_front(); } for(int i=n-k;i<=n;i++)ans=min(ans,dp[i]); return printf("%lld\n",s-ans),0; }
打开封面
下载高清视频
观看高清视频
视频下载器
【算法进阶】【贪心-过河问题】更复杂的贪心,过河问题情况详解-信息学竞赛
【算法进阶】【动态规划百练】简单状压dp与滚动数组优化 P5005 中国象棋 - 摆上马 -信息学竞赛
【算法进阶】【动态规划百练】会这一题,区间dp就掌握了!CF1771D Hossam and (sub-)palindromic tree - 信息学奥赛
【算法进阶】【动态规划-7数位动态规划】最简单的dp-数位dp!数位dp知识点与例题Segment Sum详解-信息学竞赛
【算法进阶】【字符串-AC自动机】AC自动机算法原理及实现精讲+代码 - 信息学奥赛
【算法进阶】【动态规划-8概率与期望动态规划】dp,永远的噩梦?并不是!代码最短的dp题!CF235B Let's Play Osu!-信息学竞赛
【算法进阶】【动态规划百练】思维+状态压缩动态规划CF1391D 505-信息学竞赛
【算法】贪心算法的理解和思考
【算法进阶】【动态规划百练】状态压缩动态规划+BFS P2622 关灯问题II-信息学竞赛
【算法进阶】【带权并查集/并查集复习】最后一次学习简单并查集!学不会以后各种算法都听不懂! - 信息学竞赛
【算法进阶】【严格次小生成树】Kruskal最小生成树+树上倍增详解-信息学竞赛
【算法进阶】【动态规划百练】矩阵快速幂优化动态规划P2151[SDOI2009]HH去散步-信息学竞赛
【算法进阶】【动态规划百练-IOI1998 Polygon】上古IOI动态规划题目讲解-信息学竞赛
【算法进阶】【数据结构百练】ST表 单调队列 线段树 CF1195E OpenStreetMap-信息学竞赛
【算法入门】【动态规划-2背包问题】01背包、完全背包、多重背包以及滚动数组优化、维度优化等精细讲解及伪代码展示
【算法进阶】【高斯消元】高斯消元解决n元一次方程组-信息学竞赛
【算法强化】【斜率优化动态规划】动态规划的优化之斜率优化DP-信息学竞赛
【算法进阶】【高级数据结构-替罪羊树】平衡树解法之一替罪羊树讲解-信息学竞赛
【算法进阶】【动态规划百练】状压dp货郎挑担问题CF8C Looking for Order-信息学竞赛
【算法进阶】【简单线段树题目】线段树简单练习题P2787 语文1(chin1)- 理理思维-信息学竞赛
【算法进阶】【拉格朗日插值】拉格朗日插值,解决多点确定函数问题-信息学竞赛
【算法进阶】【数论-组合初步】排列组合二项式定理Lucas定理P1350车的放置精讲-信息学竞赛
【算法入门】【动态规划-1引入及简单问题】动态规划基本思想、解题策略 P1002 过河卒 P1216 数字三角形 Number Triangles
【算法进阶】【树链剖分】树链剖分(重链剖分)精讲-信息学竞赛
【算法进阶】【有向图上的动态规划】有向图tarjan缩点与拓扑排序动态规划详解-信息学竞赛
【算法进阶】【优先队列】优先队列 ST表 NOI2010真题 P2048 [NOI2010] 超级钢琴精讲-信息学竞赛
【算法进阶】【杂题选讲】Minimum spanning tree for each edge最小生成树&树上倍增练习题-信息学竞赛
【算法进阶】【杂题选讲】简单网络流建模P2071座位安排-信息学竞赛
【算法入门】【数论基础】欧几里得算法及扩展欧几里得算法的推到及10行以内代码!精简中的精简代码!
【算法进阶】【网络流建模】dinic算法的应用,网络流建模例题-信息学竞赛
【算法进阶】【线段树的合并与分裂】合并与分裂:均摊复杂度之美-信息学竞赛
【算法入门】【图论-最短路】传递闭包floyd求最短路,4行代码?真的可以实现!理论也很简单!
【算法进阶】【前后缀优化建图】前后缀建图技巧-信息学竞赛
【算法入门】【图论-建图】图的定义、概念及建图的几种方法
【算法进阶】【可持久化字典树】可持久化Trie 树链剖分 P4592 [TJOI2018] 异或-信息学竞赛
【算法进阶】【数据结构百练】思维+树状数组+前缀和 P7868 [COCI2015-2016#2] VUDU-信息学竞赛
【算法进阶】【矩阵运算、快速幂及其应用】P3390 【模板】矩阵快速幂、P1962 斐波那契数列、P1939 【模板】矩阵加速(数列) 算法以及例题精讲
【算法进阶】【枚举技巧-折半搜索meet in the middle】折半搜索[蓝桥杯2023省A]买瓜详解-信息学竞赛
【算法进阶】【杂题选讲】luogu P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G SCC强连通分量讲解及应用
【算法进阶】【动态规划-8概率与期望动态规划(二)】简单概率与期望题目,例题P6089 [JSOI2015] 非诚勿扰-信息学竞赛