【每日一题】 3-26 数学考试
题目链接：
题意：
有 n 个数字，你可以选择两段长度为 k 的连续的区间，并且这两个区间不能重叠，每个区间的价值等于区间中 k 个数字的和，问两个区间加起来的最大价值。
题解：
考虑只取一段的情况，滑动窗口统计一下易每个点作为终点的区间价值，然后取最大值就可以了
那么我们接着来考虑取两段的情况，假设我们已经取了一段 
以 i 结束的长度为 k 的区间，为了让两段区间不重叠，我们还可以取所有结尾 
满足 
，因为我们会遍历每个位置作为 
，所以我们只需要考虑取 
或者 
其中的一种情况就可以了。
以 为例，我们只需要求出所有结尾 满足 里面的区间最大价值作为第二个区间价值，就做完了这个题目，所以我们再对 
数组做一个前缀最大值即可
注意答案可能小于 0 ，所以 ans 设小一点
代码：
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 200005;
ll a[MAXN];//原数组
ll sumk[MAXN];//前k个数字的和
ll maxnk[MAXN];//选择结尾是j=[k,i]的sum[j]的最大值
int main()
{
int T;
sc("%d", &T);
while (T--)
{
int n, k;
sc("%d%d", &n, &k);
for (int i = 1; i <= n; i++)//初始化
sumk[i] = 0;
for (int i = 1; i <= n; i++)
{
sc("%lld", &a[i]);
if (i <= k)
sumk[k] += a[i];
else
sumk[i] = sumk[i - 1] + a[i] - a[i - k];
}
maxnk[k] = sumk[k];//sumk 的前缀最大值
for (int i = k + 1; i <= n; i++)
maxnk[i] = max(maxnk[i - 1], sumk[i]);
ll ans = -1e18;
for (int i = 2 * k; i <= n; i++)//枚举第一个区间的右端点
ans = max(ans, sumk[i] + maxnk[i - k]);//另一个区间的右端点要小于等于 i-k
pr("%lld\n", ans);
}
} 
百度公司氛围 311人发布
投递百度等公司10个岗位 >
