[牛客竞赛]209809.乐团派对（线性DP）

题目传送门：乐团派对 (nowcoder.com)

思路 / Thought

首先对能力值数组进行排序，因为选人的时候顺序没要求，升序的话方便考虑，如果i可以组成乐队的话，比i小的肯定可以组成。

定义dp[i]表示到i为止可以组成的最大合法乐团数量。

接下来就可以写状态转移方程

第i个人，要么分到前面的乐队，要么分到后面的乐队。

但是第N个只能分到前面的乐队，所以输出的答案应该是dp[N - a[N]] + 1。

如果a[N] > N就输出-1。

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 9;

int a[maxn], dp[maxn];//dp[i] means from 1 to i, the count of teams

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int N;cin >> N;
	for(int i = 1;i <= N; ++ i)cin >> a[i];
	sort(a + 1, a + 1 + N);//升序 
	
	for(int i = 1;i <= N; ++ i)
    {
        dp[i] = dp[i - 1];
        if(a[i] <= i)dp[i] = max(dp[i - a[i]] + 1, dp[i - 1]);
    }
    if(a[N] <= N)cout << dp[N - a[N]] + 1 << '\n';
    else cout << -1 << '\n';
	return 0;
}