#P4265. [USACO18FEB] Snow Boots S

[USACO18FEB] Snow Boots S

题目描述

It's winter on the farm, and that means snow! There are NN tiles on the path from the farmhouse to the barn, conveniently numbered 1N1 \dots N, and tile ii is covered in fif_i feet of snow. Farmer John starts off on tile 11 and must reach tile NN to wake up the cows. Tile 11 is sheltered by the farmhouse roof, and tile NN is sheltered by the barn roof, so neither of these tiles has any snow. But to step on the other tiles, Farmer John needs to wear boots!

In his foul-weather backpack, Farmer John has BB pairs of boots, numbered 1B1 \dots B. Some pairs are more heavy-duty than others, and some pairs are more agile than others. In particular, pair ii lets FJ step in snow at most sis_i feet deep, and lets FJ move at most did_i forward in each step.

Unfortunately, the boots are packed in such a way that Farmer John can only access the topmost pair at any given time. So at any time, Farmer John can either put on the topmost pair of boots (discarding his old pair) or discard the topmost pair of boots (making a new pair of boots accessible).

Farmer John can only change boots while standing on a tile. If that tile has ff feet of snow, both the boots he takes off AND the boots he puts on must be able to withstand at least ff feet of snow. Intermediate pairs of boots which he discards without wearing do not need to satisfy this restriction.

Help Farmer John minimize waste, by determining the minimum number of pairs of boots he needs to discard in order to reach the barn. You may assume that Farmer John is initially not wearing any boots.

输入格式

The first line contains two space-separated integers NN and BB (2N,B2502 \leq N,B \leq 250). The second line contains NN space-separated integers. The iith integer is fif_i, giving the depth of snow on tile ii (0fi1090 \leq f_i \leq 10^9). It's guaranteed that f1=fN=0f_1 = f_N = 0.

The next BB lines contain two space-separated integers each. The first integer on line i+2i+2 is sis_i, the maximum depth of snow in which pair ii can step. The second integer on line i+2i+2 is did_i, the maximum step size for pair ii. It's guaranteed that 0si1090 \leq s_i \leq 10^9 and 1diN11 \leq d_i \leq N-1.

The boots are described in top-to-bottom order, so pair 11 is the topmost pair in FJ's backpack, and so forth.

输出格式

The output should consist of a single integer, giving the minimum number of boots Farmer John needs to discard. It's guaranteed that it will be possible for FJ to make it to the barn.

题目大意

到冬天了,这意味着下雪了!从农舍到牛棚的路上有NN块地砖,方便起见编号为1N1 \dots N,第ii块地砖上积了fif_i英尺的雪。 Farmer John从11号地砖出发,他必须到达NN号地砖才能叫醒奶牛们。11号地砖在农舍的屋檐下,NN号地砖在牛棚的屋檐下,所以这两块地砖都没有积雪。但是在其他的地砖上,Farmer John只能穿靴子了!

在Farmer John的恶劣天气应急背包中,总共有BB双靴子,编号为1B1 \dots B。其中某些比另一些结实,某些比另一些轻便。具体地说,第ii双靴子能够让FJ在至多sis_i英尺深的积雪中行走,能够让FJ每步至多前进did_i

不幸的是,这些靴子都套在一起,使得Farmer John在任何时刻只能拿到最上面的那一双。所以在任何时刻,Farmer John可以穿上最上面的一双靴子(抛弃原来穿着的那双),或是丢弃最上面的那一双靴子(使得可以拿到下面那一双)。

Farmer John只有在地砖上的时候才能换靴子。如果这块地砖的积雪有ff英尺,他换下来的靴子和他换上的那双靴子都要能够承受至少ff英尺的积雪。中间没有穿就丢弃的靴子无需满足这一限制。

帮助Farmer John最小化他的消耗,确定他最少需要丢弃的靴子的双数。你可以假设Farmer John在开始的时候没有穿靴子。

输入格式(文件名:snowboots.in): 第一行包含两个空格分隔的整数NNBB2N,B2502 \leq N,B \leq 250)。 第二行包含NN个空格分隔的整数。第ii个整数为fif_i,即ii号地砖的积雪深度(0fi1090 \leq f_i \leq 10^9)。输入保证f1=fN=0f_1 = f_N = 0

下面BB行,每行包含两个空格分隔的整数。第i+2i+2行的第一个数为sis_i,表示第ii双靴子能够承受的最大积雪深度。第i+2i+2行的第二个数为did_i,表示第ii双靴子的最大步长。输入保证0si1090 \leq s_i \leq 10^9以及1diN11 \leq d_i \leq 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

提示

Problem credits: Brian Dean and Dhruv Rohatgi