Snow Boots

Snow Boots
题面


题意
大意就是有n块瓦片，每一个瓦片都有一个雪的深度，第一片跟最后一片的雪深度是0. 现在有b双靴子，每一双靴子都有一个最大能经过的积雪数量和最远能跨越的瓦片数而且确保一定可以走到终点，问最少使用多少双靴子可以走到终点。.
分析
这题一开始我是准备用贪心来做的，可是我忽略一种情况。比如
0 1 4 8 8 8 8 8 1 8 8 8 8 0
4 2
3 10
8 1
如果按照一直贪心地走没有考虑到换的鞋能经过的积雪量也要大于等于当前积雪量的话就得出2这个答案。在深度为1的地方换2号鞋，就可以只扔一双走完。那其实我们在思考这个问题的时候是不是考虑了前后两个状态的转移，这就是dp的本质。dp[i]表示第i个位置所需要最小的鞋数，我们就可以从第1、2、…i-1个位置更新，然后逐步考虑这些位置。遍历更新，需要考虑是不换鞋还是换一双鞋还是换两双鞋…然后就可以得到第i个位置所需要最小双鞋数。

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=255;
const ll inf=1e9+10;
ll n,b,nd[maxn],s[maxn],wd[maxn],dp[maxn];///nd表示的实际雪的深度,wd表示鞋子可以踏的最大深度,s表示的最大距离，dp表示在第j个位置穿最少的鞋数
int main(){
	cin>>n>>b;
	for(ll i=1;i<=n;i++)
		cin>>nd[i];
	for(ll i=1;i<=b;i++)
		cin>>wd[i]>>s[i];
	for(ll i=2;i<=n; i++)
		dp[i]=inf;
	dp[1]=1;
	for(ll i=2;i<=n;i++){
		for(ll j=i-1;j>=1;j--){
			for(ll k=dp[j];k<=b;k++){
				if(wd[k]>=nd[j]&&wd[k]>=nd[i]&&i-j<=s[k])
					dp[i]=min(dp[i],k);
			}
		}
	}
	cout<<(dp[n]-1)<<endl;
	return 0;
}