题目链接 题意：已知 f(1, j) = a[j] f[i][j] = min (f[i-1][j],f[i-1][j-1]) 然后给出 n n≤1E5​​ 个数（a[i] a​i​​≤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的若干状态。。。有些状态是不会对答案有贡献的。。。这些我们就可以不考虑。。。