清点人数

问题描述

东东每个学期都会去寝室接受扫楼的任务，并清点每个寝室的人数。
每个寝室里面有 ai 个人(1 ≤ i ≤ n)。从第 i 到第 j 个宿舍一共有 sum(i, j) = a[i] + ... + a[j] 个人
这让宿管阿姨非常开心，并且让东东扫楼 m 次，每一次数第 i 到第 j 个宿舍 sum(i, j)
问题是要找到 sum(i1, j1) + ... + sum(im, jm) 的最大值。且 ix ≤ iy ≤ jx 和 ix ≤ jy ≤ jx 的情况是不被允许的。也就是说 m 段都不能相交。
注：1 ≤ i ≤ n ≤ 1e6, -32768 ≤ ai ≤ 32767 人数可以为负数。(1 ≤ n ≤ 1000000)

Input

输入 m，输入 n。后面跟着输入 n 个 ai。
处理到 EOF。

Output

输出最大和

Sample

Input: 
1 3 1 2 3
2 6 -1 4 -2 3 -2 3

Output: 
6
8

Limitation

Time limit      1000 ms
Memory limit    32768 kb

解题思路

吐个槽，这道题题面改的不怎么样，人数可以是负数？！

题意就是，一个数列，数有正有负，求最大和区间。

设数组 f[i][j] 表示前 j 个数分割成 i 段的最大值，初始化 f[i][i] = 0 。状态转移方程为：

$$f_{i, j}=max(f_{i, j-1},f_{i-1,k})+a_j，i≤k≤j$$

由于 i = j 存在，所以可能会出现 f[i][i - 1] (i - 1 个数分割成 i 个区间)，显然不行，所以需要把 f[i][i - 1]置为最小值。

本题数据量非常大，需要用滚动数组优化空间。

源代码

#include <cstdio>
#include <algorithm>
using namespace std;

const long long inF = 0x3f3f3f3f;
const long long maxN = 1000010;
long long arr[maxN];
long long dp[2][maxN];

void reSet(long long n) {
	for (long long i = 0; i <= n; i++) {
		dp[0][i] = 0;
		dp[1][i] = 0;
	}
}

void solve(long long n, long long m) {
	reSet(n);
	for (long long i = 1, k = 1; i <= m; i++, k ^= 1) {
		dp[k][i - 1] = -inF;
		long long maxPre = -inF;
		for (long long j = i; j <= n - m + i; j++) {
			maxPre = max(maxPre, dp[k ^ 1][j - 1]);
			dp[k][j] = max(dp[k][j - 1], maxPre) + arr[j];
		}
	}
	long long ans = -inF;
	for (long long i = m; i <= n; i++)
		ans = max(ans, dp[m & 1][i]);
	printf("%lld\n", ans);
}

int main() {
	long long m, n;
	while (scanf_s("%lld %lld", &m, &n) != EOF) {
		for (long long i = 1; i <= n; i++)
			scanf_s("%lld", &arr[i]);
		solve(n, m);
	}

	return 0;
}