Source:

http://acm.tju.edu.cn/toj/showp4074.html

http://codeforces.com/problemset/problem/319/C

题意：

有n棵树(n < 10^5)，每棵高度为a[i]，还有个属性b[i]。现在我们有个锯子来砍树，每用一次就需要维修，维修的费用是b[i]，i = max(已经砍完的树的id)，如果没有砍完的树，则不能维修。保证a[i]严格递增，b[i]严格递减，且a[1] = 1, b[n] = 0。求砍完所有树的最小代价。

分析：

注意到题目的条件，意味着第一次必砍第一棵树。又注意到最后一棵树的b[i] = 0，意味着我们砍了最后一棵树，所有树都砍完了。这样题目的要求就转换为最小的代价砍掉最后一棵树。

显然我们砍一棵树就砍到底，且砍的树的id一定是递增的。得到dp方程 dp[i] = min(dp[j] + (a[i]-1) * b[j]) + b[i]，dp[1] = b[1]，答案为dp[n]。可以在O(n^2)内解决问题。

实际上也就等价于dp[i] = min(dp[j] + a[i] * b[j])，dp[1] = 0，我们就这个方程进行优化。

考虑 j < k < i，现在dp[i]要选择j或k，假设k比j优，即

dp[j] + a[i] * b[j] > dp[k] + a[i] * b[k]

dp[j] - dp[k] > (b[k] - b[j]) * a[i]

(dp[j] - dp[k]) / (b[k] - b[j]) < a[i]

(dp[j] - dp[k]) / (b[j] - b[k]) > -a[i]

也就是说，对任意p点，取x = b[p], y = dp[p]， 则有：如果斜率K(jk) > -a[i]，那么k比j优。（反之j比k优，若相等则一样优）

由于这题a[i]是单调增的，也就是-a[i]是单调减的，所以一旦有K(jk) > -a[i]，之后k永远比j优，所以j可以直接舍弃了。

其实也就是最初始的那个式子，斜率K = b[p], 截距B = dp[p]，然后一系列直线，a[i]一直向右推移，决策肯定也一直是单调的，我就只考虑到这里，wa到不能自拔，一直认为是爆longlong了=。=（现在我也不懂这种考虑错哪了。。还求指教）

学习了一下斜率优化，还没太理解，多了一步：

考虑 j < k < i < p，现在要对p进行决策，

如果 K(jk) < K(ki)，则k是不可能作为最优决策的。

K(ki) = -a[p]就不说了。如果K(ki) > -a[p]，则i比k优；如果K(ki) < -a[p]，则K(jk) < -a[p]，也就是上面讨论过的情况的反面，也就是j比k优。也就是说k不可能作为最优决策。

因此可能是最优决策的序列一定是斜率单调下降的，也就是上凸性。

然后就是用单调队列来维护这个决策序列了。

 1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4  5 const int maxn = 1e5 + 100; 6 int n; 7 long long a[maxn], b[maxn], f[maxn], q[maxn]; 8  9 int main()10 {11     while(scanf("%d", &n) != EOF){12         for (int i = 1; i <= n; i++) scanf("%lld", a+i);13         for (int i = 1; i <= n; i++) scanf("%lld", b+i);14         int head, tail;15         head = tail = 0; q[tail++] = 1;16         f[1] = 0;17         for (int i = 2; i <= n; i++){18             while(head + 1 < tail){19                 int j = q[head], k = q[head+1];20                 //if (f[j] + b[j] * a[i] >= f[k] + b[k] * a[i])21                 if ((f[j] - f[k]) >= (b[k] - b[j]) * a[i]) head ++; //K(jk) > -a[i]，k更优，踢j22                 else break;23             }24             f[i] = f[q[head]] + b[q[head]] * a[i];25             while(head + 1 < tail){26                 int j = q[tail-2], k = q[tail-1];27                 if ((double)(f[j]-f[k])/(b[j]-b[k]) < (double)(f[k]-f[i])/(b[k]-b[i]))  tail --;　　//维护上凸性(开始一直wa，是因为没有这个维护过程)28                 else break;    //听说相乘爆longlong29             }30             q[tail++] = i;31         }32         printf("%lld\n", f[n]);33     }34     return 0;35 }

toj 4074 CF 319C 斜率优化dp