P6935: 雪地靴

---

【题目描述】

【题目描述】
到冬天了，这意味着下雪了！从农舍到牛棚的路上有N块地砖，方便起见编号为1…N，第ii块地砖上积了fi英尺的雪。
Farmer John从1号地砖出发，他必须到达N号地砖才能叫醒奶牛们。1号地砖在农舍的屋檐下，N号地砖在牛棚的屋檐下，所以这两块地砖都没有积雪。但是在其他的地砖上，Farmer John只能穿靴子了！
在Farmer John的恶劣天气应急背包中，总共有B双靴子，编号为1…B。其中某些比另一些结实，某些比另一些轻便。具体地说，第i双靴子能够让FJ在至多si英尺深的积雪中行走，能够让FJ每步至多前进di。
不幸的是，这些靴子都套在一起，使得Farmer John在任何时刻只能拿到最上面的那一双。所以在任何时刻，Farmer John可以穿上最上面的一双靴子（抛弃原来穿着的那双），或是丢弃最上面的那一双靴子（使得可以拿到下面那一双）。
Farmer John只有在地砖上的时候才能换靴子。如果这块地砖的积雪有f英尺，他换下来的靴子和他换上的那双靴子都要能够承受至少f英尺的积雪。中间没有穿就丢弃的靴子无需满足这一限制。
帮助Farmer John最小化他的消耗，确定他最少需要丢弃的靴子的数量。你可以假设Farmer John在开始的时候没有穿靴子。
【输入格式】（snowboots.in）：
第一行包含两个空格分隔的整数N和B（2≤N,B≤250）。
第二行包含N个空格分隔的整数。第i个整数为fi，即i号地砖的积雪深度（0≤fi≤10^9）。输入保证f1=fN=0。
下面B行，每行包含两个空格分隔的整数。第i+2行的第一个数为si，表示第i双靴子能够承受的最大积雪深度。第i+2行的第二个数为di，表示第i双靴子的最大步长。输入保证0≤si≤10^9以及1≤di≤N−1。
【输出格式】（snowboots.out）：
输出包含一个整数，为Farmer John需要丢弃的靴子的最小双数。输入保证Farmer John能够到达牛棚。
【输入样例】：
10 4
0 2 8 3 6 7 5 1 4 0
2 3
4 2
3 4
7 1
【输出样例】：
2       
 
 

题目类型~

USACO-2018-银-2月 

咻咻~

提交答案 状态 返回