almost 4 years ago

终于对斜率优化有了一点理解……

calc(x,y)<g[t] 则x比y要优。calc(x,y)的值其实就是斜率

在入队的时候,设i<j<k,若calc(k,j)<calc(j,i)【斜率的比较。即维护凸壳】则无论calc是否大于g[t],j都不会是最优决策 弹出

出队时只需要找到calc(x,y)<g[t]中最优的x即可

坑啊……注意int*int=long long 的话会爆==开心的栽在了这里半个小时……

/**************************************************************
    Problem: 1010
    User: Lavender6895
    Language: C++
    Result: Accepted
    Time:136 ms
    Memory:2368 kb
****************************************************************/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define maxn 50001
using namespace std;
int q[maxn+5]={0},c[maxn]={0};
long long f[maxn]={0},g[maxn]={0},sum[maxn]={0};
int n,l;
double calc(int x,int y)
{
    return ((double)f[x]-f[y]+g[x]*g[x]-g[y]*g[y])/(2*g[x]-2*g[y]);
}
int readln()
{
    char c;int result=0,bj=1;
    while (c!='-'&&(!(c<='9'&&c>='0'))) c=getchar();
    if (c=='-') {bj=-1;c=getchar();}
    while (c<='9'&&c>='0') {result=result*10+c-'0';c=getchar();}
    return result*bj;
}
int main()
{
n=readln();l=readln();
    long long s=0;int i,start,til,k;
    for (i=1;i<=n;i++) c[i]=readln(),s+=c[i],g[i]=s+i;
    start=1;til=1;q[start]=0;
    for (i=2;i<=n;i++)
      {
        while (start<til&&calc(q[start+1],q[start])<g[i]-l-1) start++;
        k=q[start];
        f[i]=f[k]+(g[i]-g[k]-(l+1))*(g[i]-g[k]-(l+1));
        while (start<til&&calc(i,q[til])<calc(q[til],q[til-1])) til--;
        q[++til]=i;
      }
    printf("%lld\n",f[n]);
}
← 【bzoj2553】【ac自动机】【dp】【矩阵优化】禁忌 【bzoj3196】【分块】二逼平衡树 →
 
comments powered by Disqus