牛客小白月赛27 B-乐***对

• 前言

  初见此题，便一贪为敬，不曾想，数据过强，需dp，作此篇，解此题QwQ
  

• 分析

  可以发现，如果这个人要加入团队，一定是和[1,i],[2,i]...[i-a[i],i]这些人组队，并且当前的a[i]要小于等于i，那这里就可以记下一笔

  dp[i]=max(dp[1~(i-a[i])])+1;

  但是n>1e4,n^2肯定凉凉,于是我们开始思考，能不能去掉一重循环。可以知道如果我们存下dp[1~(i-a[i])]的最大值，就可以不用循环了

• 代码

#include<bits/stdc++.h>
const int N=1e5+10;
using namespace std;
int n;
int a[N],dp[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+n+1);

    if(a[n]>n) puts("-1");
    else
    {
        for(int i=1;i<=n;i++)
        {
               if(a[i]<=i)
                   dp[i]=max(dp[i-1],dp[i-a[i]]+1);
            else dp[i]=0;
        }

        printf("%d\n",dp[n]);
    }

    return 0;
}