【BZOJ3203】[Sdoi2013]保护出题人

2015.08.10 10:13 Mon | 34次阅读 | 旧日oi | 固定链接 | 源码

Description

表示语死早……

题解

首先我们有 dp[i]=max(sum[j]/dis[j])(,这个模型很裸嘛,令x[j]=dis[j],y[j]=sum[j],那么易知我们需要维护一个支持从一边加点的上凸壳。 我们要求的点要满足如下性质。 设k为一个点和原点的斜率。 其左边的点的斜率lk>k,其右面的点的斜率rk<k,因为在凸壳上,这样的点只有一个,可以二分或者三分求出。 因为不需要从另一边删点,所以我们可以用一个栈来维护凸包。 有一些实现的细节,比如每次的点应如何变换成凸壳上的点,原点又该怎么设。

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define N 100005
const double inf=2333333333333333.0;
#define ll long long
struct node
{
    double x,y,lk,rk;
}a[N],st[N];
int n,top;
double x[N],y[N],ans,d;
bool check(node &a,node &b,node &c)
{
    return (b.x-a.x)*(c.y-a.y)<(c.x-a.x)*(b.y-a.y);
}
double calc(node &a,node &b)
{
    return (a.y-b.y)/(a.x-b.x);
}
int find()
{
    int l=1,r=top,mid;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(st[mid].lk<calc(st[0],st[mid])) l=mid+1;
        else if(st[mid].rk>calc(st[0],st[mid])) r=mid-1;
        else return mid;
    }
}
int main()
{
    //freopen("tt.in","r",stdin);
    //freopen("me.out","w",stdout);
    cin>>n>>d;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&y[i],&x[i]);
        a[i].x=a[i-1].x-d;
        a[i].y=a[i-1].y-y[i-1];
        st[0].x=a[i].x-x[i];
        st[0].y=a[i].y-y[i];
        while(top>1&&check(st[top-1],st[top],a[i])) top--;
        st[++top]=a[i];
        st[top].lk=inf;
        if(top==1) st[top].rk=-inf;
        else st[top].rk=st[top-1].lk=calc(st[top],st[top-1]);
        int k=find();
        ans+=(st[k].y-st[0].y)/(st[k].x-st[0].x);
    }
    printf("%.0lf\n",ans);
}```