CF 189DIV2 E DP + 기울기 최적화
그리고 톱을 한 번 톱질할 때마다 에너지를 보충해야 한다. 이 보충 에너지는 매번 톱질된 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 ;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.