题目:https://www.luogu.org/problemnew/show/P3195
第一次用斜率优化...其实还是有点云里雾里的;
网上的题解都很详细,我的理解就是通过把式子变形,假定一个最优解,得到的是一条直线,斜率已知;
然后找到最接近这个最优斜率的点作为答案;
同时发现斜率单调递增,所以可以用单调队列;
代码是惊人地短呢;
还有一个问题,就是下面这篇代码中注释掉的那句会WA,可是我觉得它不过是把下面一句展开了而已啊?
代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef double db;
int const maxn=;
int n,l,q[maxn];
db sum[maxn],f[maxn];
db a(int i){return sum[i]+i;}
db b(int i){return sum[i]+i+l+;}
db y(int i){return f[i]+b(i)*b(i);}
db x(int i){return b(i);}
db slope(int i,int j){return (y(i)-y(j))/(x(i)-x(j));}
int main()
{
scanf("%d%d",&n,&l);
for(int i=;i<=n;i++)
{
scanf("%lf",&sum[i]);
sum[i]+=sum[i-];
}
int head=,tail=;
for(int i=;i<=n;i++)
{
while(head<tail&&slope(q[head],q[head+])<*a(i))head++;
// f[i]=y(q[head])-2*a(i)*b(q[head])+a(i)*a(i);
f[i]=f[q[head]]+(a(i)-b(q[head]))*(a(i)-b(q[head]));
while(head<tail&&slope(q[tail-],q[tail])>slope(q[tail-],i))tail--;
q[++tail]=i;
}
printf("%lld",(long long)f[n]);
return ;
}