洛谷 P1052 过河 [ dp+ 离散化 ]

题目描述

在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0,1,…,L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为LL的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是SS到TT之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。

题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。

输入格式：

第一行有1个正整数L(1≤L≤1e9 )，表示独木桥的长度。
第二行有3个正整数S,T,M，分别表示青蛙一次跳跃的最小距离，最大距离及桥上石子的个数，其中1≤S≤T≤10,1≤M≤100。
第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。

输出格式：

一个整数，表示青蛙过河最少需要踩到的石子数。

输入样例#1：

10
2 3 5
2 3 5 6 7

输出样例#1：

2

说明

对于30%的数据，L≤10000；
对于全部的数据，L≤1e9;

思路 : 首先，不考虑数据的话，显然是一个很简单的背包状态转移方程为 $$dp[i]=min(dp[i],dp[i-j]+vis[i])(s<=j<=t)$$
但是数据是1e9的话开数组显然是不现实的 ，因此我们要考虑离散化
两点间的距离 len 大于 t 时，一定可以由 len % t 跳过来，所以最多只需要 t + len % t 种距离的状态就可以表示这两个石子之间的任意距离关系 , 对于相邻的两个位置 之间的距离 len , 如果 len % t + t 小于 len 则两个点之间的距离就是 len % t + t 否则 距离是 len

AC code :

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 200000 ;

typedef long long ll;

ll l ;
int s ,t ,n ,dp[maxn] ,v[maxn] ,vis[maxn] ;

int main() {
	scanf("%lld" ,&l) ;
	scanf("%d %d %d",& s,& t,& n) ;
	for (int i = 1 ; i <= n ; i ++ ) {
		scanf("%d",&v[i]);
	} v[++n] = l ;
	sort( v + 1 , v + n + 1 ) ;
	memset(vis ,0 ,sizeof(vis) ) ;
	int pos = 0 ,lenght = 0;
	for (int i = 1 ; i <= n ; i ++ ) {
		if ( v[i] - pos > (v[i] - pos) % t + t ) {
			lenght += (v[i] - pos) % t + t ;
		} else {
			lenght += v[i] - pos;
		}
		vis[lenght] = 1 ;
		pos = v[i] ;
	}
	memset(dp ,0x3f3f3f3f ,sizeof(dp) ) ;
	dp[0] = 0 ; lenght += t * 2 ;
	for (int i = 0 ; i <= lenght - s ; i ++ ) {
		for (int j = t ; j >= s ; j -- ) {
			dp[i + j] = min (dp[i] + vis[i] ,dp[i + j] ) ;
		}
	}
	int minn = 0x3f3f3f3f ;
	for (int i = lenght - 2 * t ; i <= lenght ; i ++ ) {
		minn = min(minn ,dp[i] ) ;
	}
//	printf("lenght = %d
",lenght) ;
//	for (int i = 0 ; i <= lenght ; i ++ ) {
//		printf("(%d ,%d )
",vis[i] ,dp[i] ) ;
//	} printf("
");
	printf("%d
",minn ) ;
	return 0;
}