浅谈斜率优化(例题特别行动队)

article/2025/8/26 23:49:39

题目描述


你有一支由 n n n名预备役士兵组成的部队,士兵从 1 1 1 n n n编号,要将他们拆分 成若干特别行动队调入战场。出于默契的考虑,同一支特别行动队中队员的编号应该连续,即为形如 ( i , i + 1 , . . . , i + k ) ( i , i + 1 , . . . , i + k ) ( i , i + 1 , . . . , i + k ) (i,i+1,...,i+k)(i, i + 1, ..., i + k)(i,i+1,...,i+k) (i,i+1,...,i+k)(i,i+1,...,i+k)(i,i+1,...,i+k)的序列。 编号为 i 的士兵的初始战斗力为 x i x_i xi一支特别行动队的初始战斗力 x 为队内 士兵初始战斗力之和,即 x x x= x i x_i xi+ x i x_i xi+ 1 1 1+…+ x i x_i xi+ k x kx kx = = = = x i x_i xi+ x i + 1 x_{i+1} xi+1+ … + x i + k x x_{i+k}x xi+kx= x i x_i xi​+ x i x_i xi+ 1 1 1​+…+ x i + k x_{i+k} xi+k​。

通过长期的观察,你总结出一支特别行动队的初始战斗力 x 将按如下经验公 式修正为 x ′ x′ x: x ′ = x′= x=a x 2 x^2 x2+ b x bx bx+ c c c,其中 a, b, c 是已知的系数 ( a < 0 ) (a<0) (a<0)。 作为部队统帅,现在你要为这支部队进行编队,使得所有特别行动队修正后 战斗力之和最大。试求出这个最大和。

例如,你有 4 名士兵, x 1 x_1 x1=2, x 2 x_2 x2=2, x 3 x_3 x3=3, x 4 x_4 x4=4, x 1 x_1 x1 = 2, x 2 x_2 x2 = 2, x 3 x_3 x3 = 3, x 4 x_4 x4 = 4 x 1 x_1 x1​=2, x 2 x_2 x2​=2, x 3 x_3 x3​=3, x 4 x_4 x4​=4。经验公式中的参数为 a = – 1 , b = 10 , c = – 20 a = –1, b = 10, c = –20 a=–1,b=10,c=–20。此时,最佳方案是将士兵组成 3 个特别行动队:第一队包含士兵 1 和士兵 2,第二队包含士兵 3,第三队包含士兵 4。特别行动队的初始战斗力分 别为 4, 3, 4,修正后的战斗力分别为 4, 1, 4。修正后的战斗力和为 9,没有其它 方案能使修正后的战斗力和更大。

题目可以概括如下

** 给你一个序列 xxx,你要将序列分成若干段,区间 [ l , r ] [l,r] [l,r]的价值是 a ( ∑ i = l r x i ) 2 + b ( ∑ i = l r x i ) + c a(\sum _{i=l}^rx_i)^2+b(\sum_{i=l}^rx_i)+c a(i=lrxi)2+b(i=lrxi)+c。求最大价值和。

很显然,这是一个斜率优化问题

斜率优化总是要从计算开始。
而在计算之前,要先推出转移方程所以对于我而言一般还没开始就放弃了
对于这个题,显然是区间划分的类型,所以会用到前缀和 s u m [ x ] sum[x] sum[x]
f ( x ) f(x) f(x)表示前x个划分结束之后的最大值,可以得到这个式子 f ( x ) = f ( j ) + a ∗ ( s u m [ x ] − s u m [ j ] ) 2 + b ( s u m [ x ] − s u m [ j ] ) + c . f(x)=f(j)+a*(sum[x]-sum[j])^2+b(sum[x]-sum[j])+c. f(x)=f(j)+a(sum[x]sum[j])2+b(sum[x]sum[j])+c.
f ( x ) f(x) f(x)来自 f ( j ) f(j) f(j),如果暴力,要 O ( n 2 ) O(n^2) O(n2)才能解决,显然 T L E TLE TLE
于是要引入一种高端大气上档次的优化— 斜率优化



  • 形如 f ( x ) = m i n f(x)=min f(x)=min{ f ( j ) + s u m [ j , x ] 2 f(j)+sum[j,x]^2 f(j)+sum[j,x]2} + c +c +c的DP,可以用斜率优化

一般设 k < j < i k<j<i k<j<i来更新从 j j j转移到 i i i比从 k k k转移到 i i i更优。
f ( k ) + s u m [ k , i ] 2 > f ( j ) + s u m [ j , i ] 2 f(k)+sum[k,i]^2>f(j)+sum[j,i]^2 f(k)+sum[k,i]2>f(j)+sum[j,i]2
可以化成 f ( j ) − f ( k ) + s u m [ j ] 2 − s u m [ k ] 2 s u m [ j ] − s u m [ k ] < 2 s u m [ i ] \frac {f(j)-f(k)+sum[j]^2-sum[k]^2}{sum[j]-sum[k]}<2sum[i] sum[j]sum[k]f(j)f(k)+sum[j]2sum[k]2<2sum[i]
一般写成 X ( j ) − X ( k ) Y ( j ) − Y ( k ) < s ( i ) \frac {X(j)-X(k)} {Y(j)-Y(k)}<s(i) Y(j)Y(k)X(j)X(k)<s(i) X ( j ) 、 Y ( j ) 分别只关于 j , s ( i ) 关于 s u m [ i ] X(j)、Y(j)分别只关于j,s(i)关于sum[i] X(j)Y(j)分别只关于j,s(i)关于sum[i]
( X ( i ) , Y ( i ) ) (X(i),Y(i)) (X(i),Y(i))看成一个点,不等式左边就成了斜率。
然后呢
可以令 g ( i , j ) g(i,j) g(i,j)表示 i i i点和 j j j点的斜率.
假设 g ( l , j ) < g ( j , k ) g(l,j)<g(j,k) g(l,j)<g(j,k)(k<j<l)
根据如果一个选手比你小还比你强你就可以退役了理论
1.如果 g ( l , j ) < s ( i ) g(l,j)<s(i) g(l,j)<s(i)那么l比j优,j不选
2.如果 g ( l , j ) > s ( i ) g(l,j)>s(i) g(l,j)>s(i)那么j比l优,可是k比j优,j不选
3.总之 g ( l , j ) < g ( j , k ) g(l,j)<g(j,k) g(l,j)<g(j,k),j就没有用。
是这样的在这里插入图片描述
所以去掉所有这样的,得到一个下凸包

是这样的在这里插入图片描述
因为如果一个选手比你小还比你强你就可以退役了
要用单调队列q维护.枚举i
如果 g ( q [ t a i l ] , q [ t a i l − 1 ] ) > g ( q [ t a i l ] , i ) g(q[tail],q[tail-1])>g(q[tail],i) g(q[tail],q[tail1])>g(q[tail],i), q [ t a i l ] q[tail] q[tail]就没有用,踢走。
如果 g ( q [ h e a d + 1 ] , g [ h e a d ] ) > s ( i ) g(q[head+1],g[head])>s(i) g(q[head+1],g[head])>s(i) 那么 q [ h e a d ] q[head] q[head]就不如 q [ h e a d + 1 ] q[head+1] q[head+1],也就没有用,踢走。
询问时队首最优。

呼。结束啦

真简单


题不可能这么简单


回到例题。

double pd(int j,int k)
{return double( (f[j]-f[k]+a*(s[j]*s[j]-s[k]*s[k])+b*(s[k]-s[j]))/double(s[j]-s[k]) );
}

这是斜率了。
这个题画风不一样,a<0.!!!求最大值!!!

X ( j ) − X ( k ) Y ( j ) − Y ( k ) > s ( i ) \frac {X(j)-X(k)} {Y(j)-Y(k)}>s(i) Y(j)Y(k)X(j)X(k)>s(i)
斜率是负的
于是它成了上凸包。

。。以下我是复制的上面的
要用单调队列q维护.枚举l
如果 g ( q [ t a i l ] , q [ t a i l − 1 ] ) < g ( l , q [ t a i l ] ) g(q[tail],q[tail-1])<g(l,q[tail]) g(q[tail],q[tail1])<g(l,q[tail])
1.如果 g ( l , q [ t a i l ] ) < s ( i ) g(l,q[tail])<s(i) g(l,q[tail])<s(i)那么q[tail]比l优,可是q[tail-1]比q[tail]优,q[tail]不选
2.如果 g ( l , q [ t a i l ] ) > s ( i ) g(l,q[tail])>s(i) g(l,q[tail])>s(i)那么l比q[tail]优,q[tail]不选
3. q [ t a i l ] q[tail] q[tail]就没有用,踢走。
如果 g ( q [ h e a d + 1 ] , g [ h e a d ] ) > s ( i ) g(q[head+1],g[head])>s(i) g(q[head+1],g[head])>s(i) 那么 q [ h e a d ] q[head] q[head]就不如 q [ h e a d + 1 ] q[head+1] q[head+1],也就没有用,踢走。
询问时队首最优。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 1000050
#define int long long
using namespace std;
int a,b,c,n,l,r;
int d[N],s[N],f[N],q[N];
double pd(int j,int k){return double( (f[j]-f[k]+a*(s[j]*s[j]-s[k]*s[k])+b*(s[k]-s[j]))/double(s[j]-s[k]) );
}signed main(){cin>>n;cin>>a>>b>>c;for(int i=1;i<=n;i++){cin>>d[i];s[i]=s[i-1]+d[i];}l=1,r=1;for(int i=1;i<=n;i++){while(l<r&&pd(q[l],q[l+1])>=2*a*s[i]*1.0)l++;int j=q[l];int x=s[i]-s[j];f[i]=f[j]+a* x*x+b*x+c;while(l<=r&&pd(q[r-1],q[r])<=pd(q[r],i))r--;q[++r]=i;}cout<<f[n];}

end


http://chatgpt.dhexx.cn/article/xPP9Htko.shtml

相关文章

numpy.meshgrid 用法说明

numpy.meshgrid(*xi, copyTrue, sparseFalse, indexingxy) return: X1, X2,..., XN 其中 *xi x1, x2,..., xn 都表示一维 array。 我们从下面这个简单的例子来看 meshgrid 做了什么&#xff1a; import numpy as npa np.array([2, 4, 8]) b np.array([3, 6])x, y np.mes…

MATLAB:Meshgrid用法

MATLAB-基础画图meshgrid - 知乎 (zhihu.com) 在MATLAB绘制三维曲面图或三维网格图时经常会用到meshgrid指令 比如&#xff1a;通常在确定向量x,y的基础上&#xff0c;使用meshgrid生成新的矩阵数据[X,Y],再输入函数Zf(X,Y),最后使用mesh或surf命令生成三维网格图或三维曲面图…

Python语言Numpy包之Meshgrid 函数

1 Meshgrid 函数的基本用法 在 Numpy 的官方文章里&#xff0c; meshgrid 函数的英文描述也显得文绉绉的&#xff0c;理解起来有些难度。可以这么理解&#xff0c; meshgrid 函数用两个坐标轴上的点在平面上画网格。 用法&#xff1a; [X,Y]meshgrid(x,y) [X,Y]meshgrid(…

matlab meshgrid函数

作用&#xff1a; 创建二维、三维矩阵 格式&#xff1a; [X,Y] meshgrid(x,y) [X,Y] meshgrid(x) [X,Y,Z] meshgrid(x,y,z) [X,Y,Z] meshgrid(x) eg: >> [x,y]meshgrid(1:1:3,5:1:6)x 1 2 31 2 3 y 5 5 56 6 6 …

【Numpy】 meshgrid()函数

np.mesharid()函数通常用来生成二维数据网格&#xff0c;例如一张灰度图片中长为x轴&#xff0c;宽为y轴&#xff0c;图中每一个像素点。 可以接受两个一维数组生成两个二维矩阵&#xff1a; np.meshgrid(np.arange(4),np.arange(4))我们生成的结果为&#xff1a; [array([[…

NumPy(十七):Meshgrid函数【应用场景:等高线、SVC中超平面的绘制】

一、Meshgrid函数 import numpy as np import matplotlib.pyplot as pltx np.linspace(0, 1, 5) y np.linspace(0, 1, 3) print("x ", x) print("-" * 50) print("y ", y) print("-" * 100)X, Y np.meshgrid(x, y) print("…

opencv-meshgrid

opencv-meshgrid 一句话描述 使用opencv::repeat函数和std::iota函数完成meshgrid功能。 小例程 cv::Mat Z cv::Mat::zeros(3, 5, CV_8UC1), X, Y;int x_length Z.cols, y_length Z.rows;std::vector<int> x(x_length);std::iota(x.begin(), x.end(), 1);X cv::re…

python扩展库numpy中函数meshgrid()的使用[当你想要两个for循环嵌套处理时,就该想到它]

看一个简单的例子&#xff1a; 设有一个3阶方阵Z&#xff0c; 其值由式子x^2 y^2生成。 x的取值为4&#xff0c;5&#xff0c;6&#xff1b; y的取值为7&#xff0c;8&#xff0c;9。 按常规的思路应该是由两个循环生成方阵Z&#xff0c;即如下的代码&#xff1a; #!/usr/bin…

np.meshgrid()

目录 1.meshgrid函数介绍2.meshgrid函数官方说明 1.meshgrid函数介绍 参数&#xff1a; *xi&#xff0c;也就是x1&#xff0c;x2&#xff0c;…&#xff0c;xn &#xff1a;表示网格坐标的一维数组。 copy&#xff1a;默认为True&#xff0c;如果为False&#xff0c;就返回原始…

【matlab】meshgrid的使用

函数参数列表 [X,Y] meshgrid(x,y) [X,Y] meshgrid(x) [X,Y,Z] meshgrid(x,y,z) [X,Y,Z] meshgrid(x) meshgrid可以生成2D或者3D的矩阵&#xff0c; 如果为2D&#xff0c;矩阵的shape为&#xff08;y.length, x.length&#xff09; 如果为3D&#xff0c;矩阵的shape为&a…

np.meshgrid

np.meshgrid参考 官方文档给出的解释 Return coordinate matrices from coordinate vectors. Make N-D coordinate arrays for vectorized evaluations of N-D scalar/vector fields over N-D grids, given one-dimensional coordinate arrays x1, x2,…, xn. 参数 indexing : …

meshgrid方法

目录 meshgrid 绘制曲面图三维网络 meshgrid meshgrid 和 mesh 方法的差别在于是否会画出栅格线 绘制曲面图 生成绘制3D图形所需的网格数据。因为在计算机中进行绘图操作时&#xff0c;往往需要一些采样点&#xff0c;然后根据这些采样点来绘制出整个图形。 涉及到x、y这两组数…

matlab meshgrid作用,【 MATLAB 】ndgrid 和 meshgrid 对比理解以及应用

目录 背景 本博文主要分析 ndgrid&#xff0c; meshgrid是附送的&#xff0c;都是类似的东西&#xff0c;学会了一个&#xff0c;另一个很容易就理解了。 为什么会对 ndgrid 感兴趣呢&#xff1f;因为对它的不理解&#xff0c;导致我少写了几篇博文&#xff0c;最后&#xff0c…

Meshgrid用法

在matlab绘制三维曲面图或三维网格图时经常会用到meshgrid指令 比如&#xff1a;通常在确定向量x,y的基础上&#xff0c;使用meshgrid生成新的矩阵数据[X,Y],再输入函数Zf(X,Y),最后使用mesh或surf命令生成三维网格图或三维曲面图。 那么meshgrid指令究竟是什么意思呢&#x…

【matlab】函数meshgrid的用法详解(生成网格矩阵)和ndgrid的区别及用法

------------------------------------------------------------------ meshgrid 函数用来生成网格矩阵&#xff0c;可以是二维网格矩阵。 exp1_1:生成二维网格&#xff0c;用法为&#xff1a;[x y]meshgrid(a b); % a 和b是一维数组&#xff0c;如a[1 2 3]; b [2 3 4]; 则生成…

Python基础(二):Numpy函数介绍:Meshgrid,mgrid,append等

文章目录 np.meshgrid函数np.mgrid函数np.append()函数 [5]参考资料 np.meshgrid函数 meshgrid函数通常使用在数据的矢量化上。它适用于生成网格型数据&#xff0c;可以接受两个一维数组生成两个二维矩阵&#xff0c;对应两个数组中所有的(x,y)对。 meshgrid的作用是&#xf…

【Python】Numpy 中 Meshgrid 函数介绍及简单应用

简单介绍Meshgrid 文字解释 Meshgrid功能为将两个坐标轴上的点转化为平面上的网格&#xff0c;即将两组一维数据分别转化为二维数据&#xff0c;原理为简单复制&#xff08;通过简单复制将以为数组转化为二维数组&#xff0c;即格点&#xff09;。 以上的详细解释&#xff1a…

图像处理之matlab中meshgrid函数用法详解

一、meshgrid()函数基本调用格式 meshgrid函数用来生成网格矩阵&#xff0c;既可以是二维网格矩阵&#xff0c;又可以是三维网格矩阵。 1、[X,Y] meshgrid(x,y) :基于向量x和y中包含的坐标返回二维网格坐标。X是一个矩阵&#xff0c;每一行是x的一个副本&#xff0c;Y也是一…

python meshgrid()理解

本文的目的是记录meshgrid()的理解过程: step1. 通过一个示例引入创建网格点矩阵; step2. 基于步骤1&#xff0c;说明meshgrid()的作用; step3. 详细解读meshgrid()的官网定义; 说明:step1和2 的数据都是基于笛卡尔坐标系的矩阵&#xff0c;目的是为了方便讨论。 step1. 通…

[MATLAB]中meshgrid函数的用法与实践(学习笔记)

今天在看点目标成像仿真程序的时候&#xff0c;看到了meshgrid函数&#xff0c;看了matlab的帮助文档后理解了一点&#xff0c;特此记录学习过程。 目录 一、meshgrid函数二、举例验证 三、创建二维网格绘制曲面图四、总结五、meshgrid函数源代码&#xff08;仅供参考&#xff…