#牛客在线求职答疑中心#DP34 前缀和
全部评论
DP34 前缀和是一种用于解决动态规划问题的方法,它通过维护一个前缀和数组来加速计算。这种方法在处理涉及区间和、区间最值等问题时非常有效。
以下是一个使用 DP34 前缀和求解区间和的示例:
```cpp
#include <iostream>
using namespace std;
const int N = 100010;
int n, m, a[N], s[N];
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];
}
while (m--) {
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", s[r] - s[l - 1]);
}
return 0;
}
```
这段代码首先读取数组的长度 `n` 和查询次数 `m`,然后输入数组的元素,并计算前缀和。在处理每个查询时,我们只需要计算 `s[r] - s[l - 1]` 即可得到区间 `[l, r]` 的和。
这种算法的时间复杂度为 O(n + m),空间复杂度为 O(n)。
送花
回复
分享
相关推荐
04-27 00:46
东南大学 管理科学与工程类 点赞 评论 收藏
转发