题意:
在一所学校里有 \(n\) 名学生和 \(m\) 个社团,社团被编号为 \(1\)~\(m\) 。第 \(i\) 个学生有一个能力值 \(p_i\) ,且属于社团 \(c_i\)(每个学生恰好属于一个社团)。
学校将要举行一个为期 \(d\) 天的活动,每天学校要举行一场程序设计比赛 —— 校长将会从每个社团中各选出一个人(如果某个社团没有人,就不选)组成一个队,令队里的学生的能力值的集合为 \(S\),则该队的总能力值为 \(mex(S)\) 。
但是由于学业繁忙,第 \(i\) 天时,第 \(k_i\) 个学生会离开社团(在校长选这一天参加比赛的学生之前)。
校长希望知道对于活动的每一天,他可能选出的队伍的总能力值最大是多少。
题解:
从后往前做,删除变成添加。
然后就变成了连续攻击游戏的增量算法。(每次新添加了一个人,就从上一个答案的下一个数开始,不断找增广路,啥时候找不到了,就是这一次的答案)
标签:CF1139E,一个,学生,Maximize,社团,Mex From: https://www.cnblogs.com/FLY-lai/p/18083910