题目描述

曙曙欢度国庆，来到五一大道发现人头攒动，这是因为大家都准备从五一广场上那个大屏幕观看新中国国庆阅兵式！这虽然是一件很喜庆的事情，可却让 CS 市的警察局长伤透了脑筋，因为人潮拥挤很容易发生安全事故。

为了防止意外以及能够及时处理安全问题。他们特意将五一大道上分成了 $N$ 等份，每一份设置一个群众集会点，总共有 $N$ 个集会点。在国庆这天每个聚集点都会聚集一定数量的群众，而同时也会有警察来管理这些集会点。因为 CS 其他很多地方都需要巡逻，所以只有有限的 $M$ 个警察能够被分配到了五一大道上，而他们的能力也有限，一个人只能管理连续的 $K$ 个集会点。

热心的曙曙决定帮忙，在给出每个集会点将要聚集的群众人数，曙曙通过编程告诉警察最多能够管理到多少群众。

如有 $10$ 个集会点，$3$ 个警察，每个警察能管理连续 $2$ 个集会点。

10 5 34 4 26 12 75 15 8 20

所以最多能够管理到 $167$ 个群众。

输入

从文件 manage.in 中读入数据。

第一行有三个数 $N$，$M$，$K$。如题所述。 接下来一行 $N$ 个数，第 $i$ 个数 $A_i$ 表示五一大道上集会点 $i$ 上的群众人数。

输出

输出到文件 manage.out 中。

输出共一行一个数，表示警察最多能管理的群众人数。

---

• 样例输入

7 4 1
2 43 32 4 64 1 10

• 样例输出

149

数据范围限制

$30\%$ 的数据： $1 \le N,M,K \le 100$，$1 \le A_i \le 20$。

$100\%$ 的数据： $1 \le N,M,K \le 1000$，$1 \le A_i \le 200000$。

代码

// 献爱心(manage) 
#include <cstdio>
#include <iostream>
using namespace std;
int dp[1005][1005];
int n, m, k, a[1005], s[1005];
int main() {
	freopen ("manage.in", "r", stdin);
	freopen ("manage.out", "w", stdout);
	scanf ("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; i++) {
		scanf ("%d", a[i]);
		// 前缀和 
		s[i] = s[i - 1] + a[i];
	}
//	dp[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) dp[i][j] = max (dp[i - 1][j], dp[max (0, i - k)][j - 1] + s[i] - s[max (0, i - k)]);
	}
	printf ("%d", dp[n][m]);
	return 0;
}

无输出，dp 学的还不太好，求调，谢谢！