题意：
给定一个长度为n的数字串,从中选取k个不重叠的子串（可以少选）,将每个串求和si
求max|s1?-?s2|?+?|s2?-?s3|?+?...?+?|sk?-?1?-?sk|(n <= 30000, k <= min(n, 200))
题解：
容易发现绝对值求和只与峰值和谷值有关
考虑设$dp_{i,j,k}，k \in [0,3]$ 分别表示当前值位于谷、谷峰间、峰、峰谷间时的最优解的值
怎么正确地转移呢？
答案是不用管谷是否为真正的谷、峰是否为真正的峰，直接转移
因为最优解时峰值一定大于等于峰谷间、谷峰间的值；谷值一定小于等于峰谷间、谷峰间的值
为什么?
我们分类讨论下
1.峰的值小于谷峰间的值：这样的话最优解应该是以谷峰间的值为峰，峰值分为峰、峰谷间两部分
2.峰值小于谷值：此时不必将值排成峰-谷-峰的形式，最优解此时显然把值排成谷-峰的形式
其它的类比下？
原文：https://www.cnblogs.com/handsome-zlk/p/14223729.html