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

解题报告

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;
}