NOIP集训-10.21总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
各种犯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
贪心，每个数有两个上界，第一个是其后一个数，第二个是其满分
然后只需从后向前贪心
然后各种特殊情况考虑到就好
-------------------------------------------------------------------------
评论 (0)
