题解 CF319C 【Kalila and Dimna in the Logging Industry】

whiteqwq · 2020-10-19 16:24:55 · 题解

CF319C Kalila and Dimna in the Logging Industry解题报告：

更好的阅读体验

题意

• 给定n棵树，高度为a_1到a_n，权值为b_1到b_n，当一颗树的a为0时就说它被砍倒了；
• 有一个电锯，每一次砍伐树会让一棵树的高度-1；
• 砍伐的费用为当前砍倒的编号的最大的树的b，第一次砍伐不需要费用；
• 保证a_i<a_{i+1},b_i>b_{i+1},a_1=1,b_n=0，求砍倒所有树的最小费用。
• 数据范围：1\leqslant n\leqslant 10^5。

分析

很显然，我们第一次砍的一定是第一棵树，且砍倒最后一棵树以后就不需要任何费用了，这样，题意就转化为如何花费最小的费用砍倒第n棵树。

有一个很显然的贪心思想，我们砍树一定从前往后砍（中间可以跳过一些树），因为我们砍这棵树一定无法更新砍树的费用。

设f_i为砍倒第i棵树的费用，那么可以列出转移方程f_i=\min_{j=1}^{i-1}\{f_j+b_j\cdot a_i\}。

这个O(n^2)一定无法通过题目，因此需要优化。

考虑斜率优化：设j,k两个i的决策点满足k<j<i，且j比k更优，那么有：

变一下形式：f_j+b_j\cdot a_i\leqslant f_k+b_k\cdot a_i \Rightarrow f_j-f_k\leqslant a_i\cdot(b_k-b_j) \Rightarrow \frac{f_j-f_k}{b_k-b_j}\leqslant a_i \Rightarrow -\frac{f_j-f_k}{b_j-b_k}\leqslant a_i \Rightarrow\frac{f_j-f_k}{b_j-b_k}\geqslant -a_i。

化成斜率式之后，由于a是递增的，因此用单调队列维护一个上凸壳就好了。

时间复杂度：O(n)。

代码

记得开\text{long long}，inf开大一点。

#include<stdio.h>
#include<string.h>
#define int long long
#define inf 1000000000000000000
const int maxn=100005;
int n,l,r;
int a[maxn],b[maxn],f[maxn],q[maxn];
inline int min(int a,int b){
    return a<b? a:b;
}
inline int x(int p){
    return b[p];
}
inline int y(int p){
    return f[p];
}
inline double slope(int a,int b){
    if(x(a)==x(b))
        return y(a)>y(b)? inf:-inf;
    return 1.0*(y(a)-y(b))/(x(a)-x(b));
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%lld",&b[i]);
    for(int i=1;i<=n;i++)
        f[i]=inf;
    f[1]=b[1],q[++r]=0;
    for(int i=1;i<=n;i++){
        while(l<r&&slope(q[l+1],q[l])>=-a[i])
            l++;
        f[i]=f[q[l]]+b[q[l]]*a[i];
        while(l<r&&slope(q[r-1],i)>=slope(q[r],q[r-1]))
            r--;
        q[++r]=i;
    }
    printf("%lld\n",f[n]);
    return 0;
}