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

CPP

#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;
}

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

文章操作

P13015 学习小组题解

题目大意

解题思路

AC code

相关推荐

评论

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

文章操作

P13015 学习小组 题解

题目大意

解题思路

AC code

相关推荐

评论

P13015 学习小组题解