分类导航
PHPJavaPythonC#C&C++RubyVBasp.NetGoPerlDjangoDelphiJspSpringLuaLaravelMybatisAspGroovyThinkPHP

codeforces319C

C&C++   发布时间：2022-04-03  发布网站：大佬教程  code.js-code.com
大佬教程收集整理的这篇文章主要介绍了codeforces319C，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
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 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 
25
input
Copy 
6
1 2 3 10 20 30
6 5 4 3 2 0
output
Copy 
138



题意：给你一把电锯，现在有编号为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("%I64d\n",f[n]);
}

大佬总结

以上是大佬教程为你收集整理的codeforces319C全部内容，希望文章能够帮你解决codeforces319C所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。
标签：
猜你在找的C&C++相关文章
其他相关热搜词更多
JavaScript字符串对象运算符count异步uisqloraclejsonpromisehttphttpsaxios常量forwhile循环Length算法