题意：给出两个数组，分别表示树的高度和树的补充能量的值。有两个人在锯树，这两个人的锯子很神奇，一次只能锯一颗树的高度1,也就是一次一颗树只减1.然后每次锯子锯完一次就要补充一下能量，这个补充的能量每次就是找到被锯完的ID最大的树，然后补充这个树的能量值。最后就是问，最少需要花费多少的能量，才能使得所有的树都被锯完。
分析：显然是个DP.考虑到N = 10 ^ 5,那么二重DP肯定是不可以的。我们假设dp[i]是第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] .
所以斜率就出来了。就可以优化了。
这题需要注意一下的就是，以前我写斜率优化一般都是一个分子，一个分母，然后优化的时候两边相乘判断。
但是这题需要注意的就是，当相乘的时候，是有可能爆long long 的
所以改用double就过了，这和平时的写法有关，当然也需要更加细心。
#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 = 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 ;
} |