c++题：<< 求和 >>

题目难度：中阶 时间限制：1000ms 内存限制：256mb

题目描述

给你一个含有n个整数的序列m，你能执行如下操作至多k次：
（1）选择两个下标i和j,满足 i mod k=j mod k (1≤i<j≤n,mod表示取余数运算)；
（2）交换m【i】 和 m【j】；
在执行完所有操作后，你必须选择k个连续的元素，然后计算出这k个元素的和，找到这k个元素的最大的和，
输入数据的第一行是一个整数t(1≤t≤600)， 表示数据组数。 每组数据含有两行信息作为你的得分。

输入格式

第一行是两个用空格隔开的整数n和 k(1≤k≤n≤100)
第二行是由空格隔开的n个整数m【1】,m【2】,…,m【n】 (0≤m【i】≤10^9)

输出格式

对于每组数据，输出一行，表示你能得到的分数

输入样例

5
3 2
5 6 0
1 1
7
5 3
7 0 4 0 4
4 2
2 7 3 4
3 3
1000000000 1000000000 999999997

输出样例

11
7
15
10
2999999997

样例解释

第一组数据，不执行任何操作，选出m【1】,m【2】两个元素相加，得到分数11
第三组数据，交换m【1】和m【4】,然后选出m【3】,m【4】,m【5】三个连续元素相加，得到分数15.

【以下回答由 GPT 生成】

我可以使用动态规划的方式来解决该问题。首先，我需要定义一个二维数组dp，其中dp[i][j]表示在前i个元素中，选择k个连续元素，能够得到的最大和为j的情况下，可以得到的分数。

然后，我需要进行状态转移。对于dp[i][j]，我有两种选择： 1. 我可以选择第i个元素作为选中的最后一个元素，则前i-1个元素中选择k-1个连续元素的最大和为j-nums[i]，所以dp[i][j] = dp[i-1][j-nums[i]] + nums[i]。 2. 我可以选择第i个元素不作为选中的最后一个元素，则前i-1个元素中选择k个连续元素的最大和为j，所以dp[i][j] = dp[i-1][j]。

最后，我需要在所有dp[n][j]中选择最大的值作为结果。

以下是C++代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int solve(vector<int>& nums, int k) {
    int n = nums.size();
    vector<vector<int>> dp(n+1, vector<int>(k+1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i-1]] + nums[i-1]);
        }
    }

    int maxScore = 0;
    for (int i = k; i <= n; i++) {
        maxScore = max(maxScore, dp[n][i]);
    }

    return maxScore;
}

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n, k;
        cin >> n >> k;

        vector<int> nums(n);
        for (int i = 0; i < n; i++) {
            cin >> nums[i];
        }

        int maxScore = solve(nums, k);
        cout << maxScore << endl;
    }

    return 0;
}

复杂度分析： - 时间复杂度：O(t * n * k)，其中t是数据组数，n是序列中元素的个数，k是每次操作的次数。最坏情况下，需要遍历所有的状态。 - 空间复杂度：O(n * k)，需要使用二维数组dp来存储状态。

【相关推荐】

• 你可以看下这个问题的回答https://ask.csdn.net/questions/7500683