4728: 【GESP2506六级】学习⼩组

题意

把 n 个人切分成若干连续小组，一个小组大小为k，贡献\(a_k\)，求划分之后总贡献最大值。

dp [i]：前 i 个人划分得到的最大总积极性。

状态转移

解释：前 j 个人处理完毕，把\(j+1\sim i\)划为一组，这一组人数是 \(i-j\)，贡献\(a_{i-j}\)。

n≤1000，\(O(n^2)\)完全可以通过。

/*
 * 试题名称：学习小组
 * 题目大意：n名同学划分若干连续学习小组，大小k的小组贡献a[k]，求总积极性最大值
 * 数据范围：n ≤ 1000，0 ≤ a_i ≤ 1e4，时间复杂度O(n^2)
 */
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1005;
int a[N];   // a[k]：小组恰好k个人的讨论积极性
int dp[N];  // dp[i]：前i个同学划分后的最大总积极性

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d", &a[i]);
    }

    dp[0] = 0;
    for(int i = 1; i <= n; ++i)
    {
        dp[i] = 0;
        // j是前j个人已经分完， j+1~i作为一组，组大小 i‑j
        for(int j = 0; j < i; ++j)
        {
            dp[i] = max(dp[i], dp[j] + a[i - j]);
        }
    }
    printf("%d\n", dp[n]);
    return 0;
}

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1005;
int n;
int a[N];
int main() {
    scanf("%d", & n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", & a[i]);
        for (int j = 1; j < i; j++)
            a[i] = max(a[i], a[j] + a[i - j]);
    }
    printf("%d\n", a[n]);
    return 0;
}