题解 bzoj[3437] 小P的牧场

题目背景

小P 是个特么喜欢玩MC 的孩纸。。。

题目描述

小P 在MC 里有n 个牧场，自西向东呈一字形排列（自西向东用1…n 编号），于是他就烦恼了：为了控制这n 个牧场，他需要在某些牧场上面建立控制站，每个牧场上只能建立一个控制站，每个控制站控制的牧场是它所在的牧场一直到它西边第一个控制站的所有牧场（它西边第一个控制站所在的牧场不被控制）（如果它西边不存在控制站，那么它控制西边所有的牧场），每个牧场被控制都需要一定的花费（毕竟在控制站到牧场间修建道路是需要资源的嘛~），而且该花费等于它到控制它的控制站之间的牧场数目（不包括自身，但包括控制站所在牧场）乘上该牧场的放养量，在第i 个牧场建立控制站的花费是ai，每个牧场i 的放养量是bi，理所当然，小P 需要总花费最小，但是小P的智商有点不够用了，所以这个最小总花费就由你来算出啦。

输入输出格式

输入格式
第一行一个整数n 表示牧场数目
第二行包括n 个整数，第i 个整数表示ai
第三行包括n 个整数，第i 个整数表示bi
输出格式
只有一行，包括一个整数，表示最小花费

输入输出样例

输入样例#1

4
2 4 2 4
3 1 4 2

输出样例#1

9

说明

样例说明
选取牧场1，3，4 建立控制站，最小费用为2+(2+1*1)+4=9。
数据范围与约定
对于10%的数据，1 <= n <= 10
对于30%的数据，1 <= n <= 1000
对于100%的数据，1 <= n <= 1000000 , 0 < ai,bi <= 10000

题解

大体思路就是，先用一个变量tot表示最大花费，然后找到一个ans表示最多节省的费用，最后输出tot-ans就好了
那么我们的状态变量f [ i ]就表示i-1的位置已经建了控制站，并且i位置也建的最小花费，再用一个sum数组记录b[ i ]的前缀和，那么我们的状态转移方程也就显而易见：

for(int i=n-1;i>=1;i--)
     for(int j=i+1;j<=n;j++)
          f[i]=max(f[i],f[j]+sum[i]*(j-i)-a[i]);

但我们发现这个题的数据竟然是如此的Jzm，这种O(n^2)的做法你不T谁T
于是我们就想到了斜率优化
当我们发现一个j，此时有一个k>j，我们如果能够证明此时在j的位置是最优解的话就能减少很多时间，方可AC
所以在这里我们要证明的就是f[ i ]从f[ j ]转移要比从f[ k ]转移能够获得的节省花费更多，即f [ j ]+sum [ i ]·( j - i )-a [ i ]>f [ k ]+sum [ i ]·( k - i )-a [ i ]
整理一下我们就能得到( f [ k ] - f [ j ] ) / ( j - k ) < sum [ i ] 这玩意打眼一看很像数学中的斜率，于是我们就有了这样的一个函数cal ( int j , int k )，表示 j 到 k 的斜率，于是我们就把每次找到的这个最优解 j 记进队列，后面的大概就不用我说了吧，直接上代码

C++代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long//不开long long死全家
using namespace std;

const int maxn=1e6+10;
ll n,tot=0,ans=0,r=0,l=1;
ll f[maxn]={0},a[maxn],b[maxn],sum[maxn]={0},q[maxn];

inline ll read(){
    ll x=0,flag=1;
    char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-')
            flag=-1;
        c=getchar();
    }
    while(c<='9' && c>='0'){
        x=x*10+(ll)(c-'0');
        c=getchar();
    }
    return x*flag;
}

inline double cal(ll j,ll k){
    return (double)(f[k]-f[j])/(double)(j-k);
}

int main(){
    ios::sync_with_stdio(0);
    n=read();
    for(ll i=1;i<=n;i++)
        a[i]=read();
    for(ll i=1;i<=n;i++)
        b[i]=read();
    for(ll i=1;i<=n;i++)
        sum[i]=sum[i-1]+b[i];
    for(ll i=1;i<=n;i++)
        tot+=b[i]*(n-i);
    tot+=a[n];
    q[++r]=n;
    for(ll i=n-1;i>=1;i--){
        while(l<r && cal(q[l],q[l+1])>sum[i])l++;
        ll j=q[l];
        f[i]=f[j]+sum[i]*(j-i)-a[i];
        ans=max(ans,f[i]);
        while(l<r && cal(q[r],i)>cal(q[r-1],q[r]))r--;
        q[++r]=i;
    }
    cout<<tot-ans<<endl;
    return 0;
}