首页 > 乐团派对
开通博客写题解
头像 溢流眼泪
发表于 2020-08-23 17:36:15
牛客小白月赛27：B题 乐团的派对 【难度】 鄙人不才，WA了8发。。 【题意】 你有 个人，**每个人有能力值 ，表示该人所在的队伍人数必须大于等于 ** 保证每个人都被分进一个队的情况下，队伍数量最多是多少？无解输出。 【数据范围】 【样例输入】 42 1 2 1 【样例输出】 3 【解 展开全文
去ta的博客 赞 (12) 回复(2) 收起
头像 Dear㉿You
发表于 2020-09-08 16:24:58
前言 初见此题，便一贪为敬，不曾想，数据过强，需dp，作此篇，解此题QwQ 分析 可以发现，如果这个人要加入团队，一定是和[1,i],[2,i]...[i-a[i],i]这些人组队，并且当前的a[i]要小于等于i，那这里就可以记下一笔 dp[i]=max(dp[1~(i-a[i])])+ 展开全文
去ta的博客 赞 (8) 回复(0) 收起
头像 AB-IN
发表于 2020-08-23 16:06:41
B 乐***对 先将数组从小到大排序，表示前个乐手最多组成多少乐队。 首先先进行一个判断，如果，那么这样会使一个乐队都组不起来。比如 其次就可以推出转移方程了 if(a[i]<=i) dp[i]=max(dp[i-1],dp[i-a[i]]+1); else 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 肖先生~
发表于 2020-08-24 12:48:30
题目描述音乐是带给大家快乐的存在，而你的目标就是组建若干支乐队，让世界听到你们的演奏！ 你目前有nn位乐手，每位乐手只能进入一个乐队，但并不是每位乐手都能担大任，因此需要团队合作。第i位乐手的能力值为a[i]，表示该位乐手所在乐队的人数必须大于等于a[i]。在保证每位乐手都被分进一个乐队的情况下，乐 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 璃墨韵
发表于 2020-08-25 10:17:22
设f[i]表示前i个人最多能组成几支乐队对于一个人a[i]，若当前的人数小于a[i]，即他在当前情况下怎样都不能组成乐队，则f[i]=0否则，我们考虑与他组队的人则至少需要a[i]个，我们可以考虑将i-a[i]的人与他分配在一组， 此时的f[i]则有i-a[i]钱最大的f值转移过来（中间多的人随便塞 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 bai_qi
发表于 2020-09-07 17:09:14
题目描述音乐是带给大家快乐的存在，而你的目标就是组建若干支乐队，让世界听到你们的演奏！ 你目前有n位乐手，每位乐手只能进入一个乐队，但并不是每位乐手都能担大任，因此需要团队合作。第i位乐手的能力值为a[i]，表示该位乐手所在乐队的人数必须大于等于a[i]。在保证每位乐手都被分进一个乐队的情况下，乐队 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”