斜率优化

题目链接 题意：已知 f(1, j) = a[j] f[i][j] = min (f[i-1][j],f[i-1][j-1]) 然后给出 n n≤1E5 个数（a[i] ai≤1E4)，给出 m组查询（m<=1E5），每组两个数 x,y 问 f(x,y) 是多少。 参考题解：茶姐的回答（下标好像搞错了，领会意思即可 官方题解 以及前置技能点是：斜率优化+线段树

题目链接 题意：n个数，分成若干段，每段的代价为 ，求最小代价。 思路：dp。 状态方程很显然个鬼。。。 dp[i] 表示处理完前面i个数的最小代价。 dp[0] = 0 ; dp[i] = min(dp[j]+(sum[i]-sum[j])^2) ( 0<j <i),sum[i]为a[i]的前缀和。

参考博客 这个东西英文好像叫做：convex hull trick Convex_hull_trick_wiki codeforces convex hull trick 简单说说我的理解：斜率优化是一种数形结合的思想。。。 对于一个dp的若干状态。。。有些状态是不会对答案有贡献的。。。这些我们就可以不考虑。。。