首页 > 乐团派对
头像 溢流眼泪
发表于 2020-08-23 17:36:15
牛客小白月赛27:B题 乐团的派对 【难度】 鄙人不才,WA了8发。。 【题意】 你有 个人,**每个人有能力值 ,表示该人所在的队伍人数必须大于等于 ** 保证每个人都被分进一个队的情况下,队伍数量最多是多少?无解输出。 【数据范围】 【样例输入】 42 1 2 1 【样例输出】 3 【解 展开全文
头像 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])])+ 展开全文
头像 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 展开全文
头像 肖先生~
发表于 2020-08-24 12:48:30
题目描述音乐是带给大家快乐的存在,而你的目标就是组建若干支乐队,让世界听到你们的演奏! 你目前有nn位乐手,每位乐手只能进入一个乐队,但并不是每位乐手都能担大任,因此需要团队合作。第i位乐手的能力值为a[i],表示该位乐手所在乐队的人数必须大于等于a[i]。在保证每位乐手都被分进一个乐队的情况下,乐 展开全文
头像 璃墨韵
发表于 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值转移过来(中间多的人随便塞 展开全文
头像 bai_qi
发表于 2020-09-07 17:09:14
题目描述音乐是带给大家快乐的存在,而你的目标就是组建若干支乐队,让世界听到你们的演奏! 你目前有n位乐手,每位乐手只能进入一个乐队,但并不是每位乐手都能担大任,因此需要团队合作。第i位乐手的能力值为a[i],表示该位乐手所在乐队的人数必须大于等于a[i]。在保证每位乐手都被分进一个乐队的情况下,乐队 展开全文