您现在的位置是：主页 > news > 微信公号嵌入网站开发/网站主题

微信公号嵌入网站开发/网站主题

admin2025/5/4 15:54:39【news】

简介微信公号嵌入网站开发,网站主题,网站页面打开速度,谷歌外贸建站多少钱单调队列优化DP 划定区间取值问题对于长度为l的区间，每s长度至少有一个数被取，使用动态规划 f(i)表示选第i个数的最小方案集合划分：可以取i-s1到i-1的各种方式因此f[i]w[i]min(f[i-m1],....,f[i-1]) 对于后面这一段min(f[i-m1~i-1])可以使…

微信公号嵌入网站开发,网站主题,网站页面打开速度,谷歌外贸建站多少钱单调队列优化DP 划定区间取值问题对于长度为l的区间，每s长度至少有一个数被取，使用动态规划 f(i)表示选第i个数的最小方案集合划分：可以取i-s1到i-1的各种方式因此f[i]w[i]min(f[i-m1],....,f[i-1]) 对于后面这一段min(f[i-m1~i-1])可以使…

单调队列优化DP

划定区间取值问题
对于长度为l的区间，每s长度至少有一个数被取，使用动态规划
f(i)表示选第i个数的最小方案
集合划分：可以取i-s+1到i-1的各种方式
因此f[i]=w[i]+min(f[i-m+1],....,f[i-1])
对于后面这一段min(f[i-m+1~i-1])可以使用单调队列优化。

凸包优化DP（斜率优化）

由状态转移方程：
$f[i]=min\{ f[j]+T_{i}(C_i-C_j)+S(C_n-C_j) \}$

$其中 j = 0, 1 . . . i - 1$

$我们可以将其整理为以C_j为自变量，f[j]为因变量的一次函数形式：$

$f(j)=(S+T_i)C_j+f(i)-T_iC_i-SC_n$

因为要最小化f(i),对于本题来说，就是找截距最小值，在图中我们可以发现只需要维护图中的凸包的下边界：
在这里插入图片描述

$凸包下边界的定义：任意两点连线，在连线上方的点都在凸包的下边界以上$
但是只维护凸包的下边界最坏会出现O(n)的情况，因此仍然需要挖掘其他信息：
$1 . 某点被取当为斜率大于 k 的第一个点的起点$
在这里插入图片描述

总结：如何在维护凸包中找到截距最小的点：

相当于在于一个单调的队列中，找到第一个大于某一个数的点。因此普遍做法是采用二分法。

其他特殊性质：

1.斜率单调递增，新加的点的横坐标也单调递增(k1<k2<k3)

在查询的时候可以将队头小于当前斜率的点全部删除(删除所有小于k的点)

在插入的时候，把队尾所有不满足要求的点全部删除（即不在凸包上）

若
$fracf2−f1C2−C1≤sumTi+Sfrac{f_2-f_1}{C_2-C_1} \le sumT_i+S$
则删除队头

2.若
$fracftt−ftt−1Ctt−Ctt−1≥fi−fttCi−Cttfrac{f_{tt}-f_{tt-1}}{C_{tt}-C_{tt-1}} \ge \frac{f_i-f_{tt}}{C_i-C_{tt}}$
则将队尾元素删去

例题：Acwing 301

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define MAXN 300010
typedef long long LL;LL c[MAXN],t[MAXN];
int s,n,m;
int q[MAXN];
LL f[MAXN];int main(){scanf("%d%d",&n,&s);for(int i=1;i<=n;i++){scanf("%lld%lld",&t[i],&c[i]);t[i]+=t[i-1],c[i]+=c[i-1];}//初始化int hh=0,tt=0;q[0]=0;for(int i=1;i<=n;i++){while(hh<tt&&(f[q[hh+1]]-f[q[hh]])<=(t[i]+s)*(c[q[hh+1]]-c[q[hh]])) hh++;int j=q[hh];f[i]=f[j]+t[i]*(c[i]-c[j])+s*(c[n]-c[j]);while(hh<tt&&(f[q[tt]]-f[q[tt-1]])*(c[i]-c[q[tt]])>=(c[q[tt]]-c[q[tt-1]])*(f[i]-f[q[tt]]))tt--;q[++tt]=i;}printf("%lld",f[n]);return 0;
}