在 F a r m e r Farmer Farmer J o h n John John 最喜欢的节日里，他想要给他的朋友们赠送一些礼物。 由于他并不擅长包装礼物，他想要获得他的奶牛们的帮助。你可能能够想到，奶牛们也不是很擅长包装礼物，而 F a r m e r Farmer Farmer J o h n John John 即将得到这一教训。
F a r m e r Farmer Farmer J o h n John John 的 N N N 头奶牛 ( 1 ≤ N ≤ 1 0 4 ) (1 \leq N \leq 10^{4}) (1≤N≤104) 排成一行，方便起见依次编号为 1 1 1 ~ N N N。 奶牛 i i i 的包装礼物的技能水平为 S i S_{i} Si。她们的技能水平可能参差不齐，所以 F a r m e r Farmer Farmer J o h n John John 决定把她的奶牛们分成若干个小组：每一组可以包含任意 不超过 K K K 头的 连续 的奶牛 ( 1 ≤ K ≤ 1 0 3 ) (1 \leq K \leq 10^{3}) (1≤K≤103)，并且一头奶牛不能属于多于一个小组。由于奶牛们会互相学习，这一组中每一头奶牛的技能水平会变成这组中 水平最高的奶牛 的技能水平。 请帮助 F a r m e r Farmer Farmer J o h n John John 求出：在他这样地安排分组的情况下，可以达到技能水平之和的最大 值。
输入的第一行包含 N N N 和 K K K。 以下 N N N 行按照 N N N 头奶牛的排列顺序 ( 1 1 1 ~ N N N) 依次给出她们的技能水平，技能水平是一个不超过 1 0 5 10^{5} 105 的正整数。
输出 F a r m e r Farmer Farmer J o h n John John通过将连续的奶牛进行分组可以达到的最大技能水平和。
7 3 1 15 7 9 2 5 10
84
在这个样例中，最优的方案是将前三头奶牛和后三头奶牛分别分为一组，中间的奶牛单独成为一组 (任意一组的奶牛数量可以小于 K K K)。 这样能够有效地将 7 7 7 头奶牛的技能水平提高至 15 、 15 、 15 、 9 、 10 、 10 、 10 15、15、15、9、10、10、10 15、15、15、9、10、10、10，和为 84 84 84。
这道题的数据，搜索肯定是不能全过的。 我们需要另想其他的方法。 那可不可以用 d p dp dp 呢? 如果可以，就得有 最优子结构 和 重叠子问题。
我们可以设 d p [ i ] dp[i] dp[i] 表示 从 第 1 1 1 头奶牛 到 第 N N N头奶牛 的最大技能水平和。 在计算 d p [ i ] dp[i] dp[i] 的时候，可以用 j j j 枚举 i − K + 1 i - K + 1 i−K+1 到 i i i 的奶牛，让 j j j ~ i i i 的这些奶牛分成一组，求出它们的技能水平和的最大值，再与前面的 d p [ j − 1 ] dp[j - 1] dp[j−1] 相加，就是当 j j j ~ i i i为一组时的最大技能水平和。 那么怎么求 j j j ~ i i i奶牛的最大技能水平呢，不过兔兔没有用 R M Q RMQ RMQ。 我们可以从 i i i ~ j j j 倒着循环枚举 S [ j ] S[j] S[j] ，与前面求出的 i i i ~ j + 1 j + 1 j+1 的最大值和 S [ j ] S[j] S[j] 做比较，就可以求出 i i i ~ j j j 奶牛的技能水平最大值了。
兔兔的代码如下(但是不要抄袭哟~)：
#include <cstdio> const int MAXN = 1e4, MAXK = 1e3; int N, K; int S[MAXN + 5]; int dp[MAXN + 5], MaxS[MAXN + 5]; // dp[i] 前i头奶牛 可以达到的技能水平之和 的 最大值 // MaxS[j] 在求解 第i头奶牛 时, 它到 第j头奶牛 的最大水平 int Max(int a, int b) { return a > b ? a : b; } // 最大值函数 Max int main() { scanf("%d %d", &N, &K); // 输入 N 和 K for (int i = 1; i <= N; i++) scanf("%d", &S[i]); // 输入 每个奶牛 的 水平S[i] for (int i = 1; i <= N; i++) { dp[i] = dp[i - 1] + S[i]; // 当前这头奶牛一头牛一组的时候, 所达到的技能水平之和 MaxS[i] = S[i]; // 第i头奶牛的水平 for (int j = i - 1; j >= i - K + 1 && j >= 1; j--) // 只用循环到i-K+1, 因为i-K及其后面的奶牛 是不可能和 第i头奶牛 在一组的 MaxS[j] = Max(MaxS[j + 1], S[j]); // 求出 第i头奶牛 到 第j头奶牛 的最大水平 for (int j = Max(1, i - K + 1); j <= i; j++) dp[i] = Max(dp[i], dp[j - 1] + (i - j + 1) * MaxS[j]); // dp状态转移 } printf("%d\n", dp[N]); // 输出答案 return 0; }