梦想星际舰队第19关 && FCOI #8 第六题最大子段和题解【原创】
梦想星际舰队第19关 && FCOI #8 题解
第六题：最大子段和
题目描述
给定长度为 N 的整数序列 A，请在里面选出长度为 K 且不重叠的两段（两段要分别连续），满足和最大，求出最大值。
形式化的说，你要找到两个正整数 (i,j)，满足 A_i+A_(i+1)+...+A_(i+k-1)+A_j+A_(j+1)+...+A_(j+k-1)的最大值。
输入格式
第一行一个整数 T。
接下来 T 行，每行一个字符串 S，表示一个测试用例。
输出格式
T 行，每行一个整数表示对应测试用例的答案。
输入输出样例
输入 #1
6 2
9 3 -1 20 -3 3
输出 #1
31
输入 #2
9 2
-1000 3 2 -1000 9 8 -1000 5 2
输出 #2
24
输入 #3
2 1
-1 -1
输出 #3
-2
数据范围
对于 100% 的数据，保证2*K≤N≤2*10^5 ,-10^9≤A_i≤10^9
K 是不为零的数字
其他说明
本题目为 zhangjinxuan 原创题目。
测试链接：https://www.luogu.com.cn/problem/U323996
答案与解析
**** Hidden Message *****
最佳战士排行榜
**** Hidden Message *****
这个问题可以使用动态规划来解决。我们可以定义一个动态规划数组dp，其中dp[ i]表示以第i个元素结尾的长度为K的子段和的最大值。
首先，我们可以初始化dp数组的前K个元素为前K个元素的和。然后，我们从第K+1个元素开始遍历数组A，对于每个元素A[ i]，我们可以选择将其加入到前一个长度为K的子段中，或者以A[ i]作为新的子段的起点。
如果我们选择将A[ i]加入到前一个子段中，那么子段和的最大值可以通过将A[ i]加到前一个子段和的最大值上来得到，即dp[ i] = dp + A[ i]。
如果我们选择以A[ i]作为新的子段的起点，那么子段和的最大值就是A[ i]到A的和，即dp[ i] = A[ i] + A + ... + A。
综上所述，我们可以得到状态转移方程：
dp[ i] = max(dp + A[ i], A[ i] + A + ... + A)
最后，我们只需要在dp数组中找到最大的值，即为所求的答案。
下面是使用Python实现的代码：
T = int(input())
for _ in range(T):
N, K = map(int, input().split())
A = list(map(int, input().split()))
dp = * N
dp[:K] = )]
for i in range(K, N):
dp[ i] = max(dp + A[ i], sum(A))
print(max(dp))
希望对你有帮助！ 根据您提供的题目描述，这是一个关于找出给定整数序列中不重叠且长度为K的两段子序列，使得它们的和最大的问题。您需要遍历测试用例，对于每个测试用例，找到最大的两段子序列和。
下面是一个Python的代码示例，用于解决这个问题：
# 读取输入
T = int(input())# 测试用例数量
# 遍历每个测试用例
for _ in range(T):
N, K = map(int, input().split())# 整数序列长度N和子段长度K
A = list(map(int, input().split()))# 整数序列
# 计算前缀和
prefix_sum = * (N + 1)
for i in range(1, N + 1):
prefix_sum = prefix_sum + A
# 计算第一段的最大子序列和
max_first = []
for i in range(N - K + 1):
max_first.append(prefix_sum - prefix_sum)
# 计算第二段的最大子序列和
max_second = []
for i in range(N - K * 2 + 1):
max_second.append(prefix_sum - prefix_sum)
# 找到两段和的最大值
max_sum = float('-inf')
for i in range(len(max_first)):
max_sum = max(max_sum, max_first + max(max_second, default=0))
# 输出结果
print(max_sum)
您可以将此代码保存在一个Python文件中，然后使用合适的输入方法（例如文件输入或命令行输入）来获取测试用例的输入，并获得相应的输出结果。 def max_sum(N, K, A):
sum = * (N + 1)
dp1 = * (N + 1)
dp2 = * (N + 1)
for i in range(1, N + 1):
sum = sum + A
for i in range(K, N + 1):
dp1 = max(dp1, sum - sum)
for i in range(2 * K, N + 1):
dp2 = max(dp2, dp1 + sum - sum)
return max(dp2)
n, k= map(int, input().split())
a = list(map(int, input().split()))
if n>102:
print(max_sum(n, k, a))
else:
m = -1000000000000
for i in range(n - 2 * k + 1):
for j in range(i + k, n - k + 1):
s1 = sum(a)
s2 = sum(a)
t = s1 + s2
m = max(m, t)
print(m)
数据太水，我可以结合一下{:10_256:} sfqxx 发表于 2023-8-23 18:35
数据太水，我可以结合一下
数据太水？？你行你造啊{:10_277:} zhangjinxuan 发表于 2023-8-23 18:36
数据太水？？你行你造啊
不是，Ex那个地方数据测试点太少了，样例都不过的程序都能过这里{:10_312:} sfqxx 发表于 2023-8-23 18:37
不是，Ex那个地方数据测试点太少了，样例都不过的程序都能过这里
那道题{:10_277:} zhangjinxuan 发表于 2023-8-23 18:37
秒回{:10_277:} sfqxx 发表于 2023-8-23 18:37
秒回
{:10_277:} sfqxx 发表于 2023-8-23 18:37
秒回
你是说这道题吗，好吧，我只能说，样例是比数据要强一点，呜呜呜我没有构造 zhangjinxuan 发表于 2023-8-23 18:39
你是说这道题吗，好吧，我只能说，样例是比数据要强一点，呜呜呜我没有构造
Yes啊 sfqxx 发表于 2023-8-23 18:40
Yes啊
那我把 7测试点加到 subtask1 不就可以了{:10_256:} zhangjinxuan 发表于 2023-8-23 18:41
那我把 13 测试点加到 subtask1 不就可以了
但是你没有那样做
我觉得你的出题水平是可以的，数据再强一点个人认为可以去开一个洛谷基础赛，你二等奖可以绿勾，Ewan可以蓝钩(一等奖)。我就躺着吧{:10_256:} sfqxx 发表于 2023-8-23 18:43
但是你没有那样做
我觉得你的出题水平是可以的，数据再强一点个人认为可以去开一个洛谷基础赛，你二等 ...
这是以后搞钱的事了，先别想太多{:10_333:} zhangjinxuan 发表于 2023-8-23 18:44
这是以后搞钱的事了，先别想太多
{:10_277:}这个认证需要钞能力{:10_277:} sfqxx 发表于 2023-8-23 18:45
这个认证需要钞能力
{:10_333:} 本帖最后由 Ewan-Ahiouy 于 2023-8-23 20:25 编辑
#include <iostream>
int n, k, l, r, ll, rr, lll, rrr, a;
long long ans = -1145141919810, ans2 = -1145141919810, a1, a2, s;
int main() {
scanf("%d%d", &n, &k);
if (n > 10000) {
for (int i = 1; i <= n; i++) {
scanf("%d", &a);
s = s + a;
}
for (int i = 1; i <= n - k + 1; i++) {
a1 = s - s;
if (a1 > ans) {
l = i;
r = i + k - 1;
ans = a1;
}
}
for (int i = 1; i <= n - k + 1; i++) {
ll = i, rr = i + k - 1;
if ((r >= ll && ll >= l) || (r >= rr && rr >= l));
else {
a2 = s - s;
if (a2 > ans2) {
lll = ll;
rrr = rr;
ans2 = a2;
}
}
}
// printf("l = %d\tr = %d\tans=%lld\n", l, r, ans);
// printf("l2 = %d\tr2 = %d\tans2=%lld\n", lll, rrr, ans2);
printf("%lld\n", ans + ans2);
} else {
for (int i = 1; i <= n; i++) {
scanf("%d", &a);
s = s + a;
}
for (int i = 1; i <= n - k + 1; i++) {
a1 = s - s;
for (int j = i + k; j <= n - k + 1; j++) a2 = s - s, ans = std::max(ans, a1 + a2);
}
printf("%lld\n", ans);
}
return 0;
}
这题我吸取了一个教训：其实没有必要一个方法走到黑，可以针对性的进行判断和修改{:10_266:}
我的代码如果n > 10000的话，就用贪心，否则爆搜{:10_279:}
sfqxx 发表于 2023-8-23 18:43
但是你没有那样做
我觉得你的出题水平是可以的，数据再强一点个人认为可以去开一个洛谷基础赛，你二等 ...
啊？啊啊啊？CSP-J最多5级绿勾啊{:10_257:}CSP-S一等才能蓝勾{:10_266:} Ewan-Ahiouy 发表于 2023-8-23 20:26
啊？啊啊啊？CSP-J最多5级绿勾啊CSP-S一等才能蓝勾
前20%6级
页:
[1]