【贪心】 导弹拦截
【题目描述】
某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统，但是这种拦截系统有一个缺陷：
虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。
某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段。
所以一套系统有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度不大于30000的正整数）。
计算要拦截所有导弹最小需要配备多少套这种导弹拦截系统。
【输入】
n颗依次飞来的高度（1≤n≤1000）。
【输出】
要拦截所有导弹最小配备的系统数k。
【输入样例】
389 207 155 300 299 170 158 65
【输出样例】
2
【提示】
输入：导弹高度： 4 3 2
输出：导弹拦截系统k=1
【贪心】区间覆盖
【题目描述】
给定一个长度为m的区间，再给出n条线段的起点和终点（本题考虑闭区间），求最少使用多少线段可以将整个区间完全覆盖。
【输入】
第一行是区间长度m。第二行是n,表示有n个可选区间。后面跟着n行数据，每行包含两个值，第一个是当前区间的起始端点值，第二个是当前区间的结束端点值。
【输出】
能覆盖m的最少的区间个数
【输入样例1】
8 6 2 6 1 4 3 6 3 7 6 8 2 4 3 5
【输出样例1】
3
【题解】会场安排
【贪心】区间选点
【题目描述】
数轴上有n个闭区间[ai, bi]，取尽量少的点，使得每个区间内都至少有一个点。（不同区间内含的点可以是同一个，1<=n<=10000，1<=ai<=bi<=10^9）。求最少点的个数。
【输入】
n
n项工作的开始与结束时间
【输出】
最多参与的工作项数
【输入样例1】
Bash
4 3 13 6 20 4 14 1 10
【输出样例1】
1
【输入样例2】
Bash
3 4 7 6 8 11 20
【输出样例2】
2
【贪心】区间调度
【题目描述】
有n项工作，每项工作分别在si时间开始，在ti时间结束。对于每项工作，你都可以选择参与与否。如果选择了参与，那么自始至终都必须全程参与。此外，参与工作的时间段不能重叠（即使是开始与结束的瞬间重叠也是不允许的）。
你的目标是参与尽可能多的工作，那么最多能参与多少项工作呢？1<=n<=100000，1<=si<=ti<=10^9。
【输入】
n
n项工作的开始与结束时间
【输出】
最多参与的工作项数
【输入样例】
5 1 3 2 5 4 7 6 9 8 10
【输出样例】
3
【题解—深搜】马走日
【题目描述】
马在中国象棋以日字形规则移动。
请编写一段程序，给定n×m大小的棋盘，以及马的初始位置(x，y)，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。
【输入】
第一行为整数T(T < 10)，表示测试数据组数。
每一组测试数据包含一行，为四个整数，分别为棋盘的大小以及初始位置坐标n,m,x,y。(0≤x≤n-1,0≤y≤m-1, m < 10, n < 10)。
【输出】
每组测试数据包含一行，为一个整数，表示马能遍历棋盘的途径总数，0为无法遍历一次。
【输入样例】
1 5 4 0 0
【输出样例】
32
【题解】背包问题3
【题目描述】
完全背包定义有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。本题要求是背包恰好装满背包时，求出最大价值总和是多少。如果不能恰好装满背包，输出NO。
【输入】
第一行： N 表示有多少组测试数据（N<7）。
接下来每组测试数据的第一行有两个整数M，V。 M表示物品种类的数目，V表示背包的总容量。(0<M<=2000，0<V<=50000)
接下来的M行每行有两个整数c，w分别表示每种物品的重量和价值(0<c<100000，0<w<100000)
【输出】
对应每组测试数据输出结果（如果能恰好装满背包，输出装满背包时背包内物品的最大价值总和。 如果不能恰好装满背包，输出NO）
【输入样例】
2 1 5 2 2 2 5 2 2 5 1
【输出样例】
NO 1
【题解】背包问题2
【题目描述】
设有 n 中物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为 m ，今从 n 种物品中选取若干件（同一物品可以多次选取），使其重量的和小于等于 m ，而价值的和为最大。
【输入】
第一行：两个整数， m （背包容量， m ≤ 200 ）和（物品数量， n ≤ 30 ）；
第二 行~到n+1 行：每行两个整数 wi ， ui ，表示每个物品的重量和价值。
【输出】
仅一行，一个数，表示最大总价值。以max=开头。
【输入样例】
10 4 2 1 3 3 4 5 7 9
【输出样例】
max=12
【题解—动态规划】背包问题1
【题目描述】
一个旅行者有一个最多能装 m 公斤物品的背包，现在有 n 件物品，它们的重量分别是 w1,w2,…,wn, 它们的价值分别为 c1,c2,…cn 。若每种物品只有一件，求旅行者能获得的最大总价值。
【输入】
第一行：两个整数 m （背包容量， m ≤ 200 ）和 n （物品数量， n ≤ 30 ）；
第二 行到第n+1 行：每行两个整数 wi,ci, 表示每个物品的重量和价值。
【输出】
一个数据，表示最大总价值。
【输入样例】
10 4 2 1 3 3 4 5 7 9
【输出样例】
12