题目地址
题意:
把正整数序列分隔为若干区间,若单个区间的元素之和为X,则其贡献为\(aX^2+bX+c\)。求所有区间的贡献之和的最大值。
分析:
斜率优化dp模板题。
这篇博客描述得很清晰(但是推出的式子不等号方向弄反了)。
整理不等式,得到斜率表达式。每到一个 i 时,可以立即获取当前的切线斜率k(假定k恒负)。对于由两个候选点连成的直线而且,设斜率为w,若w>k,则后者更优,否则前者更优。从暴力的角度讲,我们可以这样去找到目标转移点:两两枚举点,把被淘汰的一方标记,最后没被标记的点就是解。
然而对每个 i 都这样做显然复杂度不理想,于是我们先作分析,得出结论(过程自行了解):最优点一定落在最外围的凸包上。这里k为恒负,所有应该是上凸。如果一个点不在凸包上,那么无论k为何值,都一定会被淘汰。对这个凸包,我们考虑横坐标相邻的点就行了,对于不相邻的点之间连的直线,在这两点间的相邻点连线中肯定有的斜率比它高和比它低(拉格朗日中值定理)。
上凸或下凸,跟题目要最大还是最小有关,与k的正负无直接关系。找到最优点 j 后,按朴素dp式从dp[j]转移到dp[i]即可。
除了根据优劣关系筛最优点外,另一种等价思想是:将原式整理作b=max/min(y+kx),b中包含了dp[i]和其他定值,y中包含了只与j有关的值,k与i有关,x与j有关。于是问题变为找到一点(x,y),在给定的k下,截距最大/最小,那么显然直线应该切在凸包上。最后由b得到dp[i]。更详细的描述可见这篇博客,个人更喜欢这个思考方向。
思路
用斜率为负的直线切上凸包,以求得截距最大。凸包上相邻两点直线的斜率递减,可以二分查找,复杂度为\(O(nlogn)\)
由于斜率随 i 递增,每个元素至多入队一次出队一次,可用单调队列优化至\(O(n)\)。
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e6+5;
struct Pos{
ll x,y;
} q[maxn];
ll sum[maxn];
ll dp[maxn];
int main()
{
cin.tie(0)->sync_with_stdio(false);
int n;
ll a,b,c;
cin>>n>>a>>b>>c;
int l=1,r=1; //闭区间,至少有两个元素在内
q[1]={0,0}; //朴素dp是可以从0位置转移的,在斜率优化中也要按X,Y的定义如实加入起点
for(int i=1;i<=n;++i)
{
ll t;
cin>>t;
sum[i]=sum[i-1]+t;
ll k=2*a*sum[i];
while(r>l && k*(q[l+1].x-q[l].x)<q[l+1].y-q[l].y) //用乘法比较斜率(这里是最尾点与其下一个点)(不用拆括号,保证无除法即可)
++l;
dp[i]=q[l].y-k*q[l].x+a*sum[i]*sum[i]+b*sum[i]+c; //B=Y-KX,再从B中得到dp[i]
//dp[i]=q[l].f+a*(sum[i]-q[l].x)*(sum[i]-q[l].x)+b*(sum[i]-q[l].x)+c; //另一种思想,表达式等价
Pos p;
p.x=sum[i], p.y=dp[i]+a*sum[i]*sum[i]-b*sum[i];
while(r>l && (p.y-q[r].y)*(q[r].x-q[r-1].x)>(q[r].y-q[r-1].y)*(p.x-q[r].x))
--r;
q[++r]=p;
}
cout<<dp[n];
}
标签:洛谷,int,题解,ll,斜率,maxn,行动队,sum,dp
From: https://www.cnblogs.com/blover/p/17058362.html