dz论坛如何做网站地图,东莞人才网求职,万网登录,三屏合一网站建设[COCI 2017-2018-2]-San
san(1s64M)
游戏世界中有N个楼从左到右排列#xff0c;从左到右编号为1到N#xff0c;第i幢楼的高度为Hi,楼上的金币数为Gi,游戏可以从任意一个楼开始且包涵几步。每一步玩家可以从当前位置向右跳#xff08;可以跳过一些楼#xff09;但必须跳到…[COCI 2017-2018-2]-San
san(1s64M)
游戏世界中有N个楼从左到右排列从左到右编号为1到N第i幢楼的高度为Hi,楼上的金币数为Gi,游戏可以从任意一个楼开始且包涵几步。每一步玩家可以从当前位置向右跳可以跳过一些楼但必须跳到不低于当前楼的高度的楼上。他到了楼上后可以得到楼上的金币。他可以在跳任意步可以是零步后结束游戏但是要保证收到的金币数要大于等于K现在想知道共有多少不同的种方案满足游戏。两个方案不同是指至少有一个楼不一样的方案。
输入
第一行两个数N (1 ≤ N ≤ 40) and K (1 ≤ K ≤ 4·10^10 )
接下来N行每行两个正整数第i行用Hi和Gi表示第i个楼的高度和上面的金币。 (1 ≤ Hi, Gi ≤ 109 )
输出一行一个数表示方案总数。
In test cases worth 40% of total points, it will hold N ≤ 20.
SAMPLE TESTS
input input input
4 6
2 1
6 3
7 2
5 6
Output
3
样例1对应的方案 {1, 2, 3}, {1, 4} and {4}
对于40%的数据n20
对于100%的数据n40
1.n20
爆搜即可。
2.n40
solution1暴力剪枝。
solution2折半搜索法。
将n拆成两半
我们可以分别算出两个独立区间的贡献再尝试算出由左区间到右区间的贡献。
维护树状数组线段树每一次二分询问答案即可。 此题中的内存限制为64MB所以在维护时需特别注意空间。
本萌新在考试时因内存限制被卡掉10分。。。
