首页 > 代码库 > [SRM] 09 CCZ的诗
[SRM] 09 CCZ的诗
QwQ为数不多的几次有部分分的OI赛制的SRM，感谢CCZ的一屋子部分分= =
A. 模拟只会猜题意
B. 贪心只能过样例
给出n个数a[i]（1<=a[i]<=n），问最多能把这些数分成几组，使得每个数a[i]所在的组至少有a[i]个数
输入格式
第一行一个整数n，接下来n行每行一个整数分别是a[1],a[2],...,a[n]
输出格式
一行，输出答案，一个整数
分析
因为是按组分，所以顺序也就不重要了，先sort成递增
为了保证分组数最多，应该从大到小一个个满足（有点像弹飞绵羊呢）
方程为DP[i] = max( DP[i-arr[i]]+1 , DP[i-1] )
注意边界问题！
代码
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #define LL long long 5 using namespace std; 6 7 LL n; 8 LL DP[10000000]; 9 LL maxx[10000000];10 LL arr[10000000];11 12 int main(){13 scanf("%lld",&n);14 15 for(LL i = 1;i <= n;i++){16 scanf("%lld",&arr[i]); 17 }18 19 sort(arr+1,arr+1+n);20 21 for(LL i = 1;i <= n;i++){22 if(i-arr[i] < 0 || !i) maxx[i] = 0;23 else{24 25 maxx[i] = maxx[i-arr[i]]+1;26 27 if(i < n) maxx[i] = max(maxx[i],maxx[i-1]);28 }29 }30 31 printf("%lld",maxx[n]);32 33 return 0;34 }
C. 数学上来先打表
D. DP只会找规律
[SRM] 09 CCZ的诗
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。