1 条题解
-
0
一步步分析这个题目。
首先显然的，砍一个木头必须全部砍完，不然必然不优。
由于 满足单调下降，因此一定是从小到大选择一些木头去砍，直到砍掉第 根木头，这样我砍木头就都是免费的了，就可以砍掉剩余的木头。
砍树必须从小到大砍，否则如果我砍了一个 ，然后砍一个 满足 ，那么 对后面没有任何贡献，不如砍后面的再来砍 。
比较容易想到一个 的暴力 dp。
设 表示砍到第 根木头所需要的最小代价，容易得到状态转移方程。
$$f_1=b_1 \\ f_i=\min_{j=1}^{i-1} f_j+b_j\times (a_i-1)+b_i $$容易发现这个东西可以斜率优化。
假设对于 ， 比 优。
$$f_j+b_j\times(a_i-1)<f_k+b_k\times(a_i-1)\\ a_i-1<\frac{f_k-f_j}{b_j-b_k} $$直接用单调队列维护，时间复杂度 。
代码
#include<bits/stdc++.h> using namespace std; const int N=1e5+5; int n,a[N],b[N],q[N],head,tail; long long f[N]; double F(int x,int y){return 1.0*(f[y]-f[x])/(b[x]-b[y]);} 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]); f[1]=b[1]; head=tail=1; q[1]=1; for(int i=2;i<=n;i++){ while(head<tail&&F(q[head],q[head+1])<a[i]-1)head++; f[i]=f[q[head]]+1ll*(a[i]-1)*b[q[head]]+b[i]; while(head<tail&&F(q[tail-1],q[tail])>F(q[tail],i))tail--; q[++tail]=i; } printf("%lld",f[n]); }
- 1
