Snow Boots

题目描述

农场的冬天到了，这意味着下雪！从农舍到谷仓的路上有 $N$ 块地砖，方便起见编号为 $1 \dots N$，第 $i$ 块地砖上覆盖着 $f_i$ 英尺深的积雪。

Farmer John 从地砖 $1$ 出发，必须到达地砖 $N$ 才能叫醒奶牛。 地砖 $1$ 被农舍的屋檐遮住，地砖 $N$ 被谷仓的屋檐遮住，因此这两块地砖都没有积雪。但要踩在其他地砖上，Farmer John 需要穿靴子！

在他的恶劣天气背包里，Farmer John 有 $B$ 双靴子，编号为 $1 \dots B$。有些靴子更耐用，有些靴子更灵活。具体而言，第 $i$ 双靴子允许 FJ 踩在最深为 $s_i$ 英尺的雪中，并且每一步最多向前移动 $d_i$。

不幸的是，靴子的打包方式使得 Farmer John 在任何时刻只能拿到最上面那一双。因此在任意时刻，Farmer John 要么穿上最上面那双靴子（丢弃他原来穿的那双），要么丢弃最上面那双靴子（使下一双靴子变得可取用）。

Farmer John 只能在站在某块地砖上时换靴子。如果该地砖上有 $f$ 英尺深的雪，那么他脱下的靴子和他穿上的靴子都必须能够承受至少 $f$ 英尺深的雪。他直接丢弃但不穿的中间那些靴子不需要满足该限制。

请帮助 Farmer John 最小化浪费，确定他为了到达谷仓最少需要丢弃多少双靴子。你可以假设 Farmer John 起初没有穿任何靴子。

输入格式

第一行包含两个用空格分隔的整数 $N$ 和 $B$（$2 \leq N,B \leq 250$）。 第二行包含 $N$ 个用空格分隔的整数。第 $i$ 个整数为 $f_i$，表示第 $i$ 块地砖上的积雪深度（$0 \leq f_i \leq 10^9$）。保证 $f_1 = f_N = 0$。 接下来 $B$ 行每行包含两个用空格分隔的整数。第 $i+2$ 行的第一个整数是 $s_i$，表示第 $i$ 双靴子能够踩踏的最大积雪深度；第二个整数是 $d_i$，表示第 $i$ 双靴子的最大步长。 保证 $0 \leq s_i \leq 10^9$ 且 $1 \leq d_i \leq N-1$。 靴子按从上到下的顺序给出，因此第 $1$ 双是背包最上面的一双，依此类推。

输出格式

输出应为一个整数，表示 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

提示

题目鸣谢：Brian Dean 和 Dhruv Rohatgi

标签: USACO|2018|Silver

来源

USACO|2018|Silver