成都网站建设方案推广,wordpress建站dedecms,权重高的发帖平台有哪些,优秀企业网站建设哪家服务好文章目录引入acwing154 滑动窗口应用135 最大子序和1088.旅行问题AcWing 1087. 修剪草坪28AcWing 1089. 烽火传递AcWing 1090. 绿色通道AcWing 1091. 理想的正方形引入
acwing154 滑动窗口
题目链接 题解
应用 闫氏最优化问题分析法
135 最大子序和
题目#xff1a; 输入…
文章目录引入acwing154 滑动窗口应用135 最大子序和1088.旅行问题AcWing 1087. 修剪草坪28AcWing 1089. 烽火传递AcWing 1090. 绿色通道AcWing 1091. 理想的正方形引入
acwing154 滑动窗口
题目链接 题解
应用 闫氏最优化问题分析法
135 最大子序和
题目 输入一个长度为 n 的整数序列从中找出一段长度不超过 m 的连续子序列使得子序列中所有数的和最大。
题解 我们把这个问题的集合分成n份第k份表示以A[k]结尾的最大连续子序列是多少 我们以A[k]结尾为例我们从A[k]开始向前延申长度jj的范围是[1,m],我们引入前缀和S[k]表示前k个数的前缀和那么图中长度为j以A[k]结尾的连续子序列答案就是S[k]-S[k-j], 现在S[k]是固定的我们要让值最大就要使得S[k-j]最小就相当于在长度为m的区间即从[k-m,k]内找最小值,这不就把问题引入到滑动窗口 时间复杂度O(n)
1088.旅行问题
题解 题目 一个环形公路由n个车站每个站有若干升汽油有的站可能油量为零每升油可以让汽车行驶一千米。 从某个车站出发一直按顺时针或逆时针方向走遍所有的车站并回到起点。 在一开始的时候汽车内油量为零John 每到一个车站就把该站所有的油都带上起点站亦是如此行驶过程中不能出现没有油的情况。 任务判断以每个车站为起点能否按条件成功周游一周。
题解 破环成链链复制 我们从点i出发能否到i1取决于i的油量是否大于等于d[i]即i到i1的距离 所有我们规定数组w[i]a[i]-d[i] s[i]表示w[i]的前缀和 从i出发到j这个过程的油量始终0,等价于在[i,in-1]中对任意的jijin-1,均有s[j]-s[i-1]0,如果min(s[j]-s[i-1])0,就说明能到达其中i是固定的所有就是找s[j]的最小值。 这就把问题引到滑动窗口这既是单调队列优化 题目中说顺时针或逆时针有一个就行所以我们还要倒着来遍单调队列
AcWing 1087. 修剪草坪28
题解
AcWing 1089. 烽火传递
题解
AcWing 1090. 绿色通道
题解
AcWing 1091. 理想的正方形
题解
