题目描述

到冬天了，这意味着下雪了！从农舍到牛棚的路上有NN块地砖，方便起见编号为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只有在地砖上的时候才能换靴子。如果这块地砖的积雪有ff英尺，他换下来的靴子和他换上的那双靴子都要能够承受至少ff英尺的积雪。中间没有穿就丢弃的靴子无需满足这一限制。
帮助Farmer John最小化他的消耗，确定他最少需要丢弃的靴子的双数。你可以假设Farmer John在开始的时候没有穿靴子。

输入描述:

第一行包含两个空格分隔的整数和（）。
第二行包含个空格分隔的整数；第个整数为，即号地砖的积雪深度（）。输入保证。
下面行，每行包含两个空格分隔的整数。第行的第一个数为，表示第双靴子能够承受的最大积雪深度。第行的第二个数为，表示第ii双靴子的最大步长。输入保证以及。

输出描述:

输出包含一个整数，为Farmer John需要丢弃的靴子的最小双数。输入保证Farmer John能够到达牛棚。

示例1

输入
10 4
0 2 8 3 6 7 5 1 4 0
2 3
4 2
3 4
7 1
输出
2

解答

dp题目：类似求完全背包的存在性。
因为靴子只能从上开始拿，而且又要丢弃靴子数最小，
那么可以
建dp数组;
表示用第i双靴子可以走到位置j;
数组元素初始化为，表示未达到。
读入数据时，从起点开始到第一个有雪的地方前，赋值为，表示不用靴子可以走到的地方.然后两层循环搞定。详见注释。
ac代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include <vector>
#include<algorithm>
using namespace std;
typedef long long ll;
#define MAX 300
#define INF 10000000
int a[MAX];//雪的深度
int dp[MAX][MAX];
int main()
{
	int n,m;
	memset(dp,-1,sizeof(dp));
	dp[0][0] = 0;
	scanf("%d %d",&n,&m);
	for(int i = 0;i<n;i++)
	{
		scanf("%d",&a[i]);
		if(i && dp[0][i-1] == 0 && a[i] == 0)
			dp[0][i] = 0;
	}
	if(dp[0][n-1] == 0)//表示一路上都没有雪
	{
		int b,c;
		for(int i = 0;i<m;i++)
			scanf("%d %d",&b,&c);
		printf("0");
		return 0;
	}
	for(int i = 1;i<=m;i++)//第i双鞋
	{
		int deep,d;
		scanf("%d %d",&deep,&d);
		for(int j = 0;j<n;j++)//第j个位置
		{
			if(deep<a[j])//不能换鞋
			{
				//是前i-1双鞋可以经过的位置
				if(dp[i-1][j]!=-1)dp[i][j] = dp[i-1][j];
				continue;
			}
			if(dp[i-1][j]==-1 && dp[i][j]==-1)continue;//此处不是落脚点
			for(int k = 0;k <= d && k+j < n;k++)
			{
				if(deep>=a[j+k])
					dp[i][j+k] = i;
			}
		}
	}
	for(int i = 1;i<=m;i++)
	{
		if(dp[i][n-1]!=-1)
		{
			printf("%d",dp[i][n-1]-1);
			break;
		}
	}

	return 0;
}


来源：来学霸世界看看