题解 | 雪地靴-牛客假日团队赛7J题
J-雪地靴_牛客假日团队赛7
https://ac.nowcoder.com/acm/contest/997/J
题目描述
到冬天了，这意味着下雪了！从农舍到牛棚的路上有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;
数组元素初始化为
，表示未达到。
读入数据时，从起点开始到第一个有雪的地方
前，%5D)
赋值为
，表示不用靴子可以走到的地方.然后两层循环搞定。详见注释。
ac代码：
来源：来学霸世界看看
因为靴子只能从上开始拿，而且又要丢弃靴子数最小，
那么可以
建dp数组
数组元素初始化为
读入数据时，从起点开始到第一个有雪的地方
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;
} 来源：来学霸世界看看
查看16道真题和解析