洛谷 P2062 很妙又很短的DP

题意：有n个人要分成一些队伍，其中第i个人要求队伍里至少有ai个人，求最多的队伍数

n <= 1e6

设dp[i] 是前i个人能分到的最多的队伍数 dp[i] = max(dp[k]) + 1 (ai <= k < i)

维护一个dp[i]的前缀最大值这样就是O（1）的转移

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 #define LL long long
 6 #define debug(x) cout << "[" << x << "]" << endl
 7 using namespace std;
 8 
 9 const int mx = 1e6+10;
10 int dp[mx], a[mx], num[mx];
11 
12 int main(){
13     int n;
14     scanf("%d", &n);
15     for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
16     sort(a+1, a+n+1);
17     for (int i = 1; i <= n; i++){
18         if (i >= a[i]) dp[i] = num[i-a[i]]+1;
19         num[i] = max(num[i-1], dp[i]);
20     }
21     printf("%d
", dp[n]);
22     return 0;
23 }