NOIP集训-10.21总结

各种犯SB啊..总之就是考挂了,不过题并不难...
另外今天各种贪心,拍都没法拍..
-------------------------------------------------------------------------
 
跳高:SuperOj944
贪心..
首先把跳板拿来排序
第一问:考虑贪心,可以知道第一对距离超过Δh的的跳板比较低的那一个的高度就是答案
第二问:低于第一问答案的所有跳板都可以跳到
第三问:只需要每次跳得尽量高,统计次数就可以了
这道题有一个trick:可能有高度为0的跳板..
-------------------------------------------------------------------------
证明:SuperOj945
发现实际上就是一堆线段,每一个有代价,要求选一些来使得整个区间可以被覆盖,且代价最小
考虑DP,f(i)表示[1,第i个线段右端点]的答案
状态转移:f(x) = min{f(i) | i的右端点被x包含} + c(x)
其中c(x)是第x个线段的代价
然后发现这个暴力转移是n^2的
但是只是需要询问[i的左端点,i的右端点]这个区间的最小值
离散化之后用线段树维护即可
-------------------------------------------------------------------------
伪造:SuperOj946
贪心,每个数有两个上界,第一个是其后一个数,第二个是其满分
然后只需从后向前贪心
然后各种特殊情况考虑到就好
-------------------------------------------------------------------------