题目描述

到冬天了，这意味着下雪了！

从农舍到牛棚的路上有 N 块地砖，方便起见编号为 1…N，第 i 块地砖上积了 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 在开始的时候没有穿靴子。

样例

数据范围
2≤N,B≤250,
0≤fi,si≤109,
1≤di≤N−1
输入样例：
10 4
0 2 8 3 6 7 5 1 4 0
2 3
4 2
3 4
7 1
输出样例：
2

算法1

(完全背包) $O(N * V)$

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const long long N = 3260;

long long n,m;
bool f[N];
long long b[N],d[N];
long long flat[N];

int main(){

  cin >> n >> m;

  for(long long i = 1 ; i <= n ; i++)cin >> flat[i];

  for(long long i = 1 ; i <= m ;i++ )cin >> b[i] >> d[i];

  f[0] = true;
  for(long long i = 1 ; i <= m ;i++)
  {
    for(long long j = 1 ; j <= n ;j++ )
      if(flat[j]  <= b[i])
         for(long long k = j  ; k >= j - d[i] && k >= 0 ; k--)
             if(flat[k] <= b[i])f[j] =f[j] || f[k];

      if(f[n])
      {
        cout << i - 1<<endl;
        break;
      }
  }


  return 0;
}
}