https://www.luogu.org/problemnew/show/P4265

题意：有长度为n的一段路，和b双靴子，每个靴子有两个参数，每步走的最长距离和最高踩在多高的雪上，穿的靴子必须从上到下，丢掉上一个才能穿下一个，求到终点最少需要丢掉多少靴子。

思路：不能贪心！反例：1，2，3，4，100，100，100，100，100，100，第一双靴子最多踏50米，一步最多走5米，第二双靴子最多踏2米，一步50米，那么不能先第一双走到4米那里，否则就gg了。

应该用dp。

可以这样：设f(i,j):当前走到了i坐标，穿着j号靴子，是否可行，存0/1。复杂度O(n^4)

优化一下：设f(i):现在在i坐标，穿着的最小标号的靴子是f(i)号。复杂度O(n^3)

对于每一个i位置，枚举它之前的所有位置j和f(j)及之后的所有靴子k。

#include<bits/stdc++.h>
using namespace std;
#define maxn 3000

int n,b,a[maxn],s[maxn],d[maxn],minv[maxn][maxn];
int f[maxn];

int main()
{
//	freopen("input.in","r",stdin);
	cin>>n>>b;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=b;i++)cin>>s[i]>>d[i];
	f[1]=1;
	for(int i=2;i<=n;i++)f[i]=(1<<25);
	for(int i=2;i<=n;i++)
	{
		for(int j=i-1;j>=1;j--)
		{
			for(int k=f[j];k<=b;k++)
			{
				if(a[j]<=s[k]&&a[i]<=s[k]&&i-j<=d[k])
					f[i]=min(f[i],k);
			}
		}
	}
	cout<<f[n]-1<<endl;
	return 0;
}