codeforces319C

发布时间：2020-12-16 07:19:19 所属栏目：百科来源：网络整理

导读：C. Kalila and Dimna in the Logging Industry time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Kalila and Dimna are two jackals living in a huge jungle. One day they decided to joi

Kalila and Dimna are two jackals living in a huge jungle. One day they decided to join a logging factory in order to make money.

The manager of logging factory wants them to go to the jungle and cut?n?trees with heights?a1,?a2,?...,?an. They bought a chain saw from a shop. Each time they use the chain saw on the tree number?i,they can decrease the height of this tree by one unit. Each time that Kalila and Dimna use the chain saw,they need to recharge it. Cost of charging depends on the id of the trees which have been cut completely (a tree is cut completely if its height equal to 0). If the maximum id of a tree which has been cut completely is?i?(the tree that have height?ai?in the beginning),then the cost of charging the chain saw would be?bi. If no tree is cut completely,Kalila and Dimna cannot charge the chain saw. The chainsaw is charged in the beginning. We know that for each?i?<?j,?ai?<?aj?and?bi?>?bj?and also?bn?=?0?and?a1?=?1. Kalila and Dimna want to cut all the trees completely,with minimum cost.

They want you to help them! Will you?

Input

The first line of input contains an integer?n?(1?≤?n?≤?105). The second line of input contains?n?integers?a1,?an?(1?≤?ai?≤?109). The third line of input contains?n?integers?b1,?b2,?bn?(0?≤?bi?≤?109).

It‘s guaranteed that?a1?=?1,?bn?=?0,?a1?<?a2?<?...?<?an?and?b1?>?b2?>?...?>?bn.

Output

The only line of output must contain the minimum cost of cutting all the trees completely.

Please,do not write the?%lld?specifier to read or write 64-bit integers in С++. It is preferred to use the?cin,?cout?streams or the?%I64dspecifier.

Examples

input

Copy

5
1 2 3 4 5
5 4 3 2 0

output

Copy

input

Copy

6
1 2 3 10 20 30
6 5 4 3 2 0

output

Copy

题意：给你一把电锯，现在有编号为1---n的n棵树，第i棵树有两个属性：树的高度ai和到当前树充一格电的花费bi。你每次选一棵树进行砍伐，只有你将当前的树砍完后才能进行充电和砍其他树，
并且你只能到已经被砍伐的树充电。你每砍一个单位长度的树要消耗一格电，你的电锯初始有一格电，现在问你最少要多少电费可以将所有树砍完。
题目保证树的高度是递增的，充电花费是递减的。第一棵树的高度是1，最后一棵树处充电花费是0。

思路：简单的斜率优化dp

由题意易知我们开始肯定是先砍第一棵树，我们只要找到将第n棵树砍掉的最小花费就可以了，其他树我们可以无消耗砍完

易推出状态转移方程：f[i]=min(f[j]+a[i]*b[j]);（j<i）

转换为一般的直线方程

f[j]=-a[i]*b[j]+f[i]

?y =? ?kx +? b?

我们只要维护一个斜率递减的凸包就可以了??

代码：

#include<cstdio>
#include<algorithm>
#define ll long long
#define N 100010
using namespace std;
ll a[N],b[N];
int que[N];
ll f[N];
double X(int i){
    return b[i];
}
double Y(int i){
    return f[i];
}
double rate(int i,int j){
    return (Y(i)-Y(j))/(X(i)-X(j));
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%I64d",&a[i]);
    for(int i=1;i<=n;i++)
    scanf("%I64d",&b[i]);
    int head,tail;
    head=tail=1;
    f[1]=0;
    que[1]=1;
    for(int i=2;i<=n;i++){
        while(tail>head&&rate(que[head],que[head+1])>-a[i])head++;
        int j=que[head];
        f[i]=f[j]+a[i]*b[j];
        while(tail>head&&rate(que[tail],que[tail-1])<rate(que[tail],i))tail--;que[++tail]=i;
    }
    printf("%I64dn",f[n]);
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!