[已解决]梦想星际舰队第19关 && FCOI #8 第六题最大子段和题解【原创】

zhangjinxuan

梦想星际舰队第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

答案与解析

游客，如果您要查看本帖隐藏内容请回复

[/hide]

最佳战士排行榜

游客，如果您要查看本帖隐藏内容请回复

[/hide]

最佳答案

月排行榜 / 总排行榜

sfqxx

2023-8-23 18:35:00

def max_sum(N, K, A):
    sum = [0] * (N + 1)
    dp1 = [0] * (N + 1)
    dp2 = [0] * (N + 1)

    for i in range(1, N + 1):
        sum[i] = sum[i - 1] + A[i - 1]

    for i in range(K, N + 1):
        dp1[i] = max(dp1[i - 1], sum[i] - sum[i - K])

    for i in range(2 * K, N + 1):
        dp2[i] = max(dp2[i - 1], dp1[i - K] + sum[i] - sum[i - K])

    return max(dp2[K:])

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[i:i + k])
            s2 = sum(a[j:j + k])
            t = s1 + s2
            m = max(m, t)

    print(m)

数据太水，我可以结合一下

跳转到最佳答案楼层

isdkz

这个问题可以使用动态规划来解决。我们可以定义一个动态规划数组dp，其中dp[ i]表示以第i个元素结尾的长度为K的子段和的最大值。

首先，我们可以初始化dp数组的前K个元素为前K个元素的和。然后，我们从第K+1个元素开始遍历数组A，对于每个元素A[ i]，我们可以选择将其加入到前一个长度为K的子段中，或者以A[ i]作为新的子段的起点。

如果我们选择将A[ i]加入到前一个子段中，那么子段和的最大值可以通过将A[ i]加到前一个子段和的最大值上来得到，即dp[ i] = dp[i-1] + A[ i]。

如果我们选择以A[ i]作为新的子段的起点，那么子段和的最大值就是A[ i]到A[i+K-1]的和，即dp[ i] = A[ i] + A[i+1] + ... + A[i+K-1]。

综上所述，我们可以得到状态转移方程：
dp[ i] = max(dp[i-1] + A[ i], A[ i] + A[i+1] + ... + A[i+K-1])

最后，我们只需要在dp数组中找到最大的值，即为所求的答案。

下面是使用Python实现的代码：

T = int(input())
for _ in range(T):
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    dp = [0] * N
    dp[:K] = [sum(A[:K])]
    
    for i in range(K, N):
        dp[ i] = max(dp[i-1] + A[ i], sum(A[i-K+1:i+1]))
    
    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 = [0] * (N + 1)
    for i in range(1, N + 1):
        prefix_sum[i] = prefix_sum[i - 1] + A[i - 1]

    # 计算第一段的最大子序列和
    max_first = []
    for i in range(N - K + 1):
        max_first.append(prefix_sum[i + K] - prefix_sum[i])

    # 计算第二段的最大子序列和
    max_second = []
    for i in range(N - K * 2 + 1):
        max_second.append(prefix_sum[i + 2 * K] - prefix_sum[i + K])

    # 找到两段和的最大值
    max_sum = float('-inf')
    for i in range(len(max_first)):
        max_sum = max(max_sum, max_first[i] + max(max_second[i:], default=0))

    # 输出结果
    print(max_sum)

您可以将此代码保存在一个Python文件中，然后使用合适的输入方法（例如文件输入或命令行输入）来获取测试用例的输入，并获得相应的输出结果。

sfqxx

def max_sum(N, K, A):
    sum = [0] * (N + 1)
    dp1 = [0] * (N + 1)
    dp2 = [0] * (N + 1)

    for i in range(1, N + 1):
        sum[i] = sum[i - 1] + A[i - 1]

    for i in range(K, N + 1):
        dp1[i] = max(dp1[i - 1], sum[i] - sum[i - K])

    for i in range(2 * K, N + 1):
        dp2[i] = max(dp2[i - 1], dp1[i - K] + sum[i] - sum[i - K])

    return max(dp2[K:])

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[i:i + k])
            s2 = sum(a[j:j + k])
            t = s1 + s2
            m = max(m, t)

    print(m)

数据太水，我可以结合一下

zhangjinxuan

sfqxx 发表于 2023-8-23 18:35
数据太水，我可以结合一下

数据太水？？你行你造啊

sfqxx

zhangjinxuan 发表于 2023-8-23 18:36
数据太水？？你行你造啊

不是，Ex那个地方数据测试点太少了，样例都不过的程序都能过这里

zhangjinxuan

sfqxx 发表于 2023-8-23 18:37
不是，Ex那个地方数据测试点太少了，样例都不过的程序都能过这里

那道题

sfqxx

zhangjinxuan 发表于 2023-8-23 18:37

秒回

zhangjinxuan

sfqxx 发表于 2023-8-23 18:37
秒回

zhangjinxuan

sfqxx 发表于 2023-8-23 18:37
秒回

你是说这道题吗，好吧，我只能说，样例是比数据要强一点，呜呜呜我没有构造

sfqxx

zhangjinxuan 发表于 2023-8-23 18:39
你是说这道题吗，好吧，我只能说，样例是比数据要强一点，呜呜呜我没有构造

Yes啊

zhangjinxuan

sfqxx 发表于 2023-8-23 18:40
Yes啊

那我把 7测试点加到 subtask1 不就可以了

sfqxx

zhangjinxuan 发表于 2023-8-23 18:41
那我把 13 测试点加到 subtask1 不就可以了

但是你没有那样做

我觉得你的出题水平是可以的，数据再强一点个人认为可以去开一个洛谷基础赛，你二等奖可以绿勾，Ewan可以蓝钩(一等奖)。我就躺着吧

zhangjinxuan

sfqxx 发表于 2023-8-23 18:43
但是你没有那样做

我觉得你的出题水平是可以的，数据再强一点个人认为可以去开一个洛谷基础赛，你二等 ...

这是以后搞钱的事了，先别想太多

sfqxx

zhangjinxuan 发表于 2023-8-23 18:44
这是以后搞钱的事了，先别想太多

这个认证需要钞能力

zhangjinxuan

sfqxx 发表于 2023-8-23 18:45
这个认证需要钞能力

Ewan-Ahiouy

#include <iostream>
int n, k, l, r, ll, rr, lll, rrr, a[200011];
long long ans = -1145141919810, ans2 = -1145141919810, a1, a2, s[200011];
int main() {
    scanf("%d%d", &n, &k);
    if (n > 10000) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            s[i] = s[i - 1] + a[i];
        }
        for (int i = 1; i <= n - k + 1; i++) {
            a1 = s[i + k - 1] - s[i - 1];
            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[i + k - 1] - s[i - 1];
                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[i]);
            s[i] = s[i - 1] + a[i];
        }
        for (int i = 1; i <= n - k + 1; i++) {
            a1 = s[i + k - 1] - s[i - 1];
            for (int j = i + k; j <= n - k + 1; j++) a2 = s[j + k - 1] - s[j - 1], ans = std::max(ans, a1 + a2);
        }
        printf("%lld\n", ans);
    }

    return 0;
}

这题我吸取了一个教训：其实没有必要一个方法走到黑，可以针对性的进行判断和修改

我的代码如果n > 10000的话，就用贪心，否则爆搜

Ewan-Ahiouy

sfqxx 发表于 2023-8-23 18:43
但是你没有那样做

我觉得你的出题水平是可以的，数据再强一点个人认为可以去开一个洛谷基础赛，你二等 ...

啊？啊啊啊？CSP-J最多5级绿勾啊CSP-S一等才能蓝勾

sfqxx

Ewan-Ahiouy 发表于 2023-8-23 20:26
啊？啊啊啊？CSP-J最多5级绿勾啊CSP-S一等才能蓝勾

前20%6级