NOIP集训-10.15总结

------------------------------------------------------------------
电话号码:SuperOjP928
模拟题...
 
------------------------------------------------------------------
Segment Erasing : SuperOjP929
 
考虑DP:
先按左端点排序,一样的按右端点排
f(x) 表示前x条线段最多能保留多少条
g(x) 表示前x条线段保留最多的时候有多少种选法
状态转移:
f(x) = max{f[y] + 1 | y在x左边且与x无交点}
g(x) = sigma(y=1,x-1且f(y)+1=f(x)) g(y)
 
------------------------------------------------------------------
电路设计:SuperOjP930
 
考虑贪心:每次把剩余数最多的m个拿去做成一个玩具
实现上可以使用优先队列
 
------------------------------------------------------------------