CF740B Alyona and flowers 题解

Content

有 \(n\) 个数 \(a_1,a_2,a_3,...,a_n\)，给定 \(m\) 个区间，你可以选择一些区间使得它们的总和最大（也可以不选），求这个最大的总和。

数据范围：\(1\leqslant n,m\leqslant 100,-100\leqslant a_i\leqslant 100\)。

Solution

我们利用前缀和来求出每个区间的元素的和：设 \(s_i\) 表示前 \(i\) 个数的和，\([l,r]\) 为要表示的区间，那么这个区间的和就是 \(s_r-s_{l-1}\)。

然后我们将每个区间里的所有元素的和排序，然后按从大到小取，一旦取到了负数或者取完了，那我们就不取了，直接输出选的这些区间的总和。

Code

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int n, m, a[107], s[107], ss[107], ans;

bool cmp(int a, int b) {

	return a > b;

}

int main() {

	scanf("%d%d", &n, &m);

	for(int i = 1; i <= n; ++i) {

		scanf("%d", &a[i]);

		s[i] = s[i - 1] + a[i];

	}

	for(int i = 1; i <= m; ++i) {

		int l, r;

		scanf("%d%d", &l, &r);

		ss[i] = s[r] - s[l - 1];

	}

	sort(ss + 1, ss + m + 1, cmp);

	for(int i = 1; i <= m; ++i) {

		if(ss[i] <= 0)	break;

		ans += ss[i];

	}

	printf("%d", ans);

}

巴特西

CF740B Alyona and flowers 题解

Content

Solution

Code

最新文章

热门文章