P1052 [NOIP2005 提高组] 过河

P1052 [NOIP2005 提高组] 过河

传送门

题意:

青蛙想从0处到达L处，路上有m块石子，问最少踩多少块石子可以过河（可以踩石子之外的地方）。

思路：

暴力dp比较好想，这样做是O(l)，l最大1e9，肯定超时。但这题石头少，可以考虑离散化。
离散化方案可以抽象成这样一个问题：有两个数i，i+1，从x开始，每次对x加i或者加（i+1），可以得到哪些数，然后会发现x+i*(i+1）之后的所有数都可以得到，于是我们将两点距离大于i*(i+1)的石子都减去i*(i+1)，在这题上面，我们考虑st的做法，若两点距离大于st，则一直减小t倍距离直到两点距离小于t，但考虑到可能存在s==t的情况，我们再加t就好了。

#include
using namespace std;
#define ll long long
#define endl 'n'
ll a[110];
ll dp[110000];
mapvis;
ll New[110000];

int main()
{
	ll l;
	cin>>l;
	ll s,t,m;
	cin>>s>>t>>m;
	for(int i = 1; i <= m; i++)
	{
		cin>>a[i];
	}
	sort(a+1,a+1+m);
	ll L = 0;
	for(int i = 1; i <= m; i++)
	{
		if(a[i]-a[i-1] > s*t)
		{
			L+=(a[i]-a[i-1])%t+t;
			New[L]++;
		}
		else
		{
			L+=(a[i]-a[i-1]);
			New[L]++;
		}
	}
	for(int i = 0; i <= 100000; i++)dp[i] = 1110;
	dp[0] = 0;
	for(int i = 0; i <= L; i++)
	{
		for(int j = s; j <= t; j++)
		{
			dp[i+j] = min(dp[i]+New[i+j], dp[i+j]);
		}
	}
	ll ans = 1110;
	for(int i = L;i <= L+t-1; i++)ans = min(ans,dp[i]);
	cout<