CF 319C(Kalila and Dimna in the Logging Industry-기울기 DP, 포크 LL 오버플로우 주의)
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 = 0and 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, a2, ..., 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.
Sample test(s)
input
5
1 2 3 4 5
5 4 3 2 0
output
25
input
6
1 2 3 10 20 30
6 5 4 3 2 0
output
138
이 문제는 슬래시DP(555...그냥 3문제 할걸)
방정식을 나는 쓰지 않겠다
롱롱이 넘쳐나는데 오전 내내 Bug을 De하고 나서야 발견했어요. 저는...
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<cctype>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define MEMI(a) memset(a,127,sizeof(a))
#define MEMi(a) memset(a,128,sizeof(a))
#define MAXN (100000+10)
#define size (tail-head+1)
int n;
long long a[MAXN],b[MAXN],f[MAXN]={0};
struct node
{
int i;
long long x,y;
node(){}
node(int _i):i(_i),x(b[i]),y(f[i]){}
friend long double k(node a,node b){return (long double)(a.y-b.y)/(long double)(a.x-b.x); }
}q[MAXN];
int head=1,tail=1;
struct V
{
long long x,y;
V(node a,node b):x(b.x-a.x),y(b.y-a.y){}
friend long long operator*(V a,V b){return ((double)a.x/a.y-(double)b.x/b.y)>0?1:-1; }
};
int main()
{
// freopen("CF319C.in","r",stdin);
// freopen("CF319C.out","w",stdout);
cin>>n;
For(i,n) cin>>a[i];
For(i,n) cin>>b[i];
f[1]=b[1];
q[1]=node(1);
Fork(i,2,n)
{
while (size>=2&&k(q[head],q[head+1])>1-a[i] ) head++;
int j=q[head].i;
f[i]=f[j]+(long long)(a[i]-1)*(long long)b[j]+b[i];
while (size>=2&&(V(q[tail-1],q[tail])*V(q[tail],node(i))>0)) tail--; //
q[++tail]=node(i);
}
//For(i,n) cout<<b[i]<<' ';cout<<endl;
//For(i,n) cout<<f[i]<<' ';cout<<endl;
cout<<f[n]<<endl;
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.