题解：P13015 [GESP202506 六级] 学习小组

S_Y_B_S · 2025-06-30 09:25:21 · 题解

P13015 学习小组 题解

题目大意

有 n 个人，现将其划分成若干个小组，每个小组根据人数可以产生若干的贡献，求最大贡献和。

解题思路

一道简单的 dp，适合初学者练习。

看到题面很容易想到背包，但是因为题意的差异，背包的状态设计并不是完全契合本题的（其实背包也能写只不过比较玄学）。

所以让我们自己动手，丰衣足食（绝对不是不会打板子）。

• 状态设计

  相对简单，求什么我们就设什么，故设 f_i 为将前 i 人划分小组后产生的最大贡献。

• 状态转移

  注意数据范围 1 \le n \le 1000，所以放弃大脑直接设计 n^2 转移。

  对于 f_i:

  要么这 i 个人自成一组，要么用剩下 i-j 个人成为一组。

  故得：

  f_i = \max \begin{cases} a_i \\ \max (f_j + a_{i-j}) & 1 \le j < i \end{cases}

  答案即为 f_n。

AC code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e3+5;
int n,a[N],f[N];
int main()
{
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i = 1;i<=n;i++) cin>>a[i];
    for(int i = 1;i<=n;i++){
        f[i] = a[i];
        for(int j = 1;j<i;j++)
            f[i] = max(f[i],f[j]+a[i-j]);
    }
    cout<<f[n];
    return 0;
}