[USACO18FEB]Snow Boots S(G题)
中文链接:
洛谷P4265
题意:
思路:
dp题目:类似求完全背包的存在性。
因为靴子只能从上开始拿,而且又要丢弃靴子数最小,
那么可以
建dp数组dp[B][N];
dp[i][j] = 1表示用第i双靴子可以走到位置j;
数组元素初始化为-1,表示未达到。
读入数据时,从起点开始到第一个有雪的地方(j)前,dp[0][0~(j-1)]赋值为0,表示不用靴子可以走到的地方.然后两层循环搞定。详见注释。
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;
}