跳房子 Meet in the Middle

思想 解题报告

题目描述

一条直线上依次有N个房子，每个房子有一个高度Hi，以及楼顶上的金币数Gi。
你可以从任意一个房子上开始，向右边跳。可以跳到右侧任意一个高度不低于当前楼顶高度的楼顶上。并获得该楼顶的金币。
要求至少获取X个金币，问有多少种不同的跳跃方法。

输入

第一行两个整数N和K，表示房子数和需要的金币数。
接下来N行，每行两个整数Hi和Gi，表示第i个房子的高度和金币数。

输出

一个整数，表示不同的跳跃方法数。

样例输入

4​ ​6
2​ ​1
6​ ​3
7​ ​2
5​ ​6

2​ ​7
4​ ​6
3​ ​5

4​ ​15
5​ ​5
5​ ​12
6​ ​10
2​ ​1

样例输出

3

0

4

提示

【样例1解释】

有3种跳跃方法：{1,​ ​2,​ ​3},​ ​{1,​ ​4}​ ​和​{4}.

数据范围

40%的数据，$N<=20$

100%的数据，$N<=40, 1<=X<=4*10^10, 1<=Hi,Gi<=10^9$

题解

X比较大，所以不能直接背包解

这是一类物品较少，背包容量极大的特殊背包问题

显然40%的数据可以直接DFS暴力求解，可是100%的数据显然暴力会超时，怎么办呢？

数据范围是暴力的2倍，有一种特殊的方法用空间换取时间，能把范围缩小1倍——Meet in the Middle

Meet in the Middle做法

Meet in the Middle 就是把原问题分成两个部分，分别暴力求解各个部分后合并答案

对于这道题，我们合并时需要考虑是否符合高度的限制，所以我们对于前一半，每种方案需要记录所得金额&最后一个，对于后一半，每种方案需要记录所得金额&第一个

然后排序+合并即可

代码

https://paste.ubuntu.com/p/yYg4tXHXM3/

Meet in the Middle衍生问题

4.最小点覆盖
给定一个有n(n <= 30)个节点的图，找到一个最小的点集，使得图中的每一条边至少有一个顶点在这个点集中。（提示：复杂度O(3^(n/2)）

5.正方形栅栏
给定一个数组L，代表n个木板的长度。请回答是否存在一种方法，使用所有的木板构成一个正方形栅栏且不损坏也不重叠。（提示：复杂度O(4^n/2)）

6.拼图
8拼图是在一个有8个板子和1个空位置的3*3拼板上滑动的游戏，在每一步你只能移动一个与空的位置正交相邻的板子到空的位置上。游戏开始时板子和空位置随机配置，目标是用最少的移动将拼版移动成指定的配置。找到一个有效的算法来解决（提示：每一个位置最多31次移动可解决）。下图我们让可以看到解决8拼图的一系列的移动。

7.反转问题
给定两个相同长度的字符串S和T。请指出是否能够从S得到T，使用4种子串翻转操作。（提示：复杂度O(n^5)）

参考资料

https://blog.csdn.net/qq_30927651/article/details/57083910