让人迷惑的斜率优化

回复帖子

@天命之路 2020-05-22 22:16 回复

就以P3195 为例,维护凸壳时为何不能取等?

#include<cstdio>
#include<iostream>
#include<cstdlib>
using namespace std;
const int N=50005;
long long f[N],sumc[N],c[N],n,l,g[N],k[N],j1,j2,j3,pre[N];
int que[N],head=1,tail=1;
inline long long squ(long long x)
{
    return 1ll*x*x;
}
template <typename T>
inline void Ckmin(T &x,T y)
{
    if(x>y) x=y;
}
int main()
{

    f[0]=0;
    scanf("%lld%lld",&n,&l);
    for(int i=1;i<=n;i++) scanf("%lld",&c[i]),sumc[i]=sumc[i-1]+c[i];
    for(int i=1;i<=n;i++) g[i]=i+sumc[i]-1-l,k[i]=i+sumc[i];
//  for(int i=1;i<=n;i++)
//  for(int j=0;j<i;j++)
//  Ckmin(f[i],f[j]+squ(i-j-1+sumc[i]-sumc[j]-l));
    head=tail=1;
    for(int i=1;i<=n;i++)
    {

        while(j1=que[tail-2],j2=que[tail-1],j3=i-1,head<tail&&
        (f[j3]+squ(k[j3])-f[j2]-squ(k[j2]))*(k[j2]-k[j1])<
        (f[j2]+squ(k[j2])-f[j1]-squ(k[j1]))*(k[j3]-k[j2])) tail--;  //这一行
        que[tail++]=i-1;
        while(j1=que[head],j2=que[head+1],head<tail&&((f[j2]+squ(k[j2])-f[j1]-squ(k[j1]))<2*g[i]*(k[j2]-k[j1])))
        head++;   //这一行
        int p=que[head];
        f[i]=f[p]+squ(g[i]-k[p]);
        pre[i]=p;
    }
    //printf("sumc g k f pre\n");
    //for(int i=1;i<=n;i++) printf("%d %d %d %d %d\n",sumc[i],g[i],k[i],f[i],pre[i]);
    cout<<f[n];

}

在注释标记的那两行中,为何不能写“<=”?

@天命之路 2020-05-22 22:30 回复 举报

我是认为,如果出现相等,那就是三个决策点共线(斜率相等),那完全可以将后面的点弹出(个人拙见)

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。