[BZOJ] 3437 小P的牧场

题目背景

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

题目描述

小P 在MC 里有n 个牧场，自西向东呈一字形排列（自西向东用1…n 编号），于是

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

输入输出格式

输入格式

第一行一个整数n 表示牧场数目

第二行包括n 个整数，第i 个整数表示$$a_i$$

第三行包括n 个整数，第i 个整数表示$$b_i$$

输出格式

只有一行，包括一个整数，表示最小花费

输入输出样例

输入样例

4
2 4 2 4
3 1 4 2

输出样例

说明

样例解释

选取牧场1，3，4 建立控制站，最小费用为2+( 2 + 1 * 1 ) + 4 = 9。

数据范围与约定

对于10%的数据，$$ 1 \leq n \leq 10 $$;

对于30%的数据，$$1 \leq n \leq 1000 $$;

对于100%的数据，$$ 1 \leq n \leq 10^7 $$ ,$$ 0 < a_i,b_i \leq 10^5 $$.

思路

动态规划+斜率优化

定义：$$f_i$$表示在$$i$$处造控制站，使得花费最小。

转移方程为：$$ fi=min(f{j-1}+\sum_{k=j}^{i}b_k \times (i-k))+a_i)$$

这显然过不了.所以我们去观察对于一个$$i$$,以及$$j,k$$这两种决策.

如果$$k$$比$$j$$优,则有:$$f{j-1}-f{k-1}+\sum{l=j}^{k-1}b_l\times (i-l) \geq 0$$

用前缀和求$$\sum_{k=j}^{i}b_k \times (i-k)$$

定义:$$sum_i$$,表示$$n$$到$$i$$的总放养数;$$g_i$$表示$$n$$到$$i$$的所有农场都到$$n$$的消费.

那么：$$\sum{k=j}^{i}b_k \times (i-k) = g_j-g{k+1}-(sumj-sum{k+1}) \cdot (i-k)$$

转移方程就变成了：$$f{j-1}-f{k-1}+g_j-g_k-(sum_j-sum_k)\cdot (n-i+1)\geq 0$$

得出：$$i\geq \frac{f{k-1}-f{j-1}+g_k-g_j+(sum_j-sum_k)\cdot (n+1)}{sum_j-sum_k}$$

继而转化成斜率优化问题~~并用单调队列维护~~

代码

#include <bits/stdc++.h>
const int M=1000005;
#define LL long long
using namespace std;

LL f[M],sum[M],g[M];
int a[M],b[M],q[M],n;

double Op(int j,int k)
{
    return f[k-1]-f[j-1]-g[j]+g[k]+(1.0*sum[j]-sum[k])*(n+1);
}

double Po(int j,int k)
{
    return sum[j]-sum[k];
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)    scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)    scanf("%d",&b[i]);
    for(int i=n;i>=1;i--)    sum[i]=sum[i+1]+b[i];
    for(int i=n;i>=1;i--)    g[i]=g[i+1]+1LL*b[i]*(n-i+1);
    int L=0,R=0;
    for(int i=1;i<=n;i++)
    {
        while(L<R-1 && Op(q[R-2],q[R-1])*Po(q[R-1],i)>=Op(q[R-1],i)*Po(q[R-2],q[R-1]))
            R--;
        q[R++]=i;
        while(L<R-1    &&    Op(q[L],q[L+1])<=i*Po(q[L],q[L+1]))
            L++;
        int id=q[L];
        f[i]=f[q[L]-1]+(g[id]-g[i])-(sum[id]-sum[i])*(n-i+1)+a[i];
    }
    cout<<f[n]<<endl;
}

[BZOJ]小P的牧场