CF 189DIV2 E DP + 기울기 최적화

제목: 나무의 높이와 나무의 보충 에너지의 값을 나타내는 두 개의 수조를 제시한다.두 사람이 나무를 톱질하고 있는데, 이 두 사람의 톱은 신기하게도 한 번에 한 개의 나무의 높이만 톱질할 수 있다. 즉, 한 번에 한 개의 나무가 1만 줄어든다.
그리고 톱을 한 번 톱질할 때마다 에너지를 보충해야 한다. 이 보충 에너지는 매번 톱질된 ID가 가장 큰 나무를 찾아서 이 나무의 에너지 값을 보충하는 것이다.
마지막으로 최소한 얼마의 에너지를 들여야만 모든 나무를 다 톱질할 수 있느냐고 물었다.
분석: 분명히 DP입니다.N=10^5를 감안하면 이중DP는 안 될 것이다.우리는 dp[i]가 첫 번째 나무가 톱질된 총 비용이라고 가정하면 dp[i]=min(dp[i], dp[j]+a[i]*b[j])이다.
여기 i는 일중순환이 필요하고 j는 일중순환이 필요하기 때문에 TLE를 긍정합니다.
뒤의 계수를 고려하면, 우리는 분명히 사율 최적화를 사용하여 이 문제를 최적화할 수 있다.
dp[j] + a[i] * b[j] < dp[k] + a[i] * b[k]. => (dp[j] - dp[k])/(b[k] - b[j]) < a[i] .
그래서 경사율이 나왔어요.최적화할 수 있습니다.
이 문제에서 주의해야 할 것은 이전에 내가 쓴 경사율 최적화는 일반적으로 한 분자, 한 분모였다. 그리고 최적화할 때 양쪽을 곱해서 판단했다.
그러나 이 문제는 곱할 때 롱롱롱을 터뜨릴 수 있다는 점에 주의해야 한다.
그래서 더블로 바꿨으니 평소의 작법과 관련이 있으니 더욱 세심해야 한다.

#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Max 2505
#define FI first
#define SE second
#define ll unsigned __int64
#define PI acos(-1.0)
#define inf 0x3fffffff
#define LL(x) ( x << 1 )
#define bug puts("here")
#define PII pair<int,int>
#define RR(x) ( x << 1 | 1 )
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )

using namespace std;
#define N 1111111

ll a[N] ;
ll b[N] ;
ll dp[N] ;
int qe[N] ;
ll getU(int j ,int k){//  
    return dp[j] - dp[k] ;
}
ll getD(int j ,int k){//  
    return b[k] - b[j] ;
}
double fk(int j ,int k){
    return (double)(dp[j] - dp[k]) / (b[k] - b[j]) ;
}
ll getDP(int i ,int j){
    return dp[j] + b[j] * a[i] ;
}
int main() {
    int n ;
    cin >> n ;
    for (int i = 1 ; i <= n ; i ++ )cin >> a[i] ;
    for (int i = 1 ; i <= n ; i ++ )cin >> b[i] ;
    mem(dp , -1) ;
    int l = 0 , r = 0 ;
    qe[r ++ ] = 1 ;
//    dp[0] = 0 ;
    dp[1] = 0 ;
    for (int i = 2 ; i <= n ; i ++ ){
        while(l + 1 < r && fk(qe[l + 1] , qe[l]) <= a[i]) l ++ ;
        dp[i] = getDP(i , qe[l]) ;
        //        long long  。    。
//        while(l + 1 < r && getU(i , qe[r - 1]) * getD(qe[r - 1] ,qe[r - 2]) <=
//                getU(qe[r - 1] , qe[r - 2]) * getD(i , qe[r - 1])) r -- ;
        while(l + 1 < r && fk(i , qe[r - 1]) <= fk(qe[r - 1] , qe[r - 2])) r -- ;
        qe[r ++ ] = i ;
    }
    cout << dp[n] << endl ;
    return 0 ;
}