CodeForces - 320E Kalila and Dimna in the Logging Industry

题意：你有要拿一把锯子砍树。锯子有有电和没电两个状态，只有在有电的时候才能工作，每次工作都可以砍1单位高度的树，然后就会没电。没电后要充电才能工作。充电有代价，代价为，当前已经砍倒的下标最大的树对应的b[i]。已知a数组递增且a[1]=1，b数组递减且b[n]=0，求砍倒所有树的最小代价。

解：显然我们只要砍倒第n棵树后就可以无限充电，所以设dp[i]为砍倒 i 所消耗的最小代价，答案为dp[n]。于是有转移dp[i]=min(dp[j]+b[j]*a[i])。接下来用一种叫斜率优化的东西优化一下。设有 j 和k，如果 k 比j更优，则有dp[j]+b[j]*a[i]>dp[k]+b[k]*a[k]，移项得(dp[j]-dp[k])/(b[k]-b[j])>a[i]，那么就可以用单调队列维护(dp[j]-dp[k])/(b[k]-b[j])，这看起来像个斜率，因此也叫斜率优化。

单调队列的写法和之前有点不同。

代码：

#include <bits/stdc++.h>
using namespace std;
#define maxx 100005
#define maxn 25
#define maxm 205
#define ll long long
#define inf 1000000009
#define mod 2520
ll a[maxx]={0},b[maxx]={0};
ll dp[maxx]={0};
int q[maxx]={0};
double cal(int j,int k){
    return ((double)dp[j]-dp[k])/(b[k]-b[j]);
}
signed 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=1,tail=1;
    q[1]=1;
    for(int i=2;i<=n;i++){
        while(head<tail&&cal(q[head],q[head+1])<a[i]) head++;
        dp[i]=dp[q[head]]+b[q[head]]*a[i];
        while(head<tail&&cal(q[tail],i)<=cal(q[tail-1],q[tail])) tail--;
        q[++tail]=i;
    }
    printf("%I64d\n",dp[n]);
    return 0;
}
//dp[i][j]=min(dp[j]+b[j]*a[i])