洛谷P1052过河

题目

不看数据范围的话是一个很简单的DP，可是加上数据范围之后就之前的做法就不行了。

所以我们考虑一下路径压缩。

小数据Code

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

int l, m, s, t, dp[100010];

int flag[100010];

int main()

{

    scanf("%d%d%d%d", &l, &s, &t, &m);

    for (int i = 1; i <= m; i++)

    {

        int a;

        scanf("%d", &a);

        flag[a] = 1;

    }

    for (int i = 1; i <= l; i++)

    {

    	dp[i] = 21474836;

        for (int j = max(i - t, 0); j <= i - s; j++)

            dp[i] = min(dp[i], dp[j] + flag[i]);

    }

    printf("%d", dp[l]);

}

大数据Code

#include <iostream>

#include <cstring>

#include <algorithm>

#include <cstdio>

#define ha s * t

#define N 100111

#define inf 214748364

#define int long long

using namespace std;

int l, m, s, t, dp[N], ans = inf * 10, r;

int data[N], a[N], b[N];

inline void init()

{

	scanf("%lld%lld%lld%lld", &l, &s, &t, &m);

    for (int i = 1; i <= m; i++)

    	cin >> data[i];

    sort(data + 1, data + 1 + m);

	if (s == t)

	{

		int ans = 0;

		for (int i = 1; i <= m; i++)

			if (!(data[i] % s)) ans++;

		printf("%lld", ans);

		exit(0);

	}

	for (int i = 1; i <= m; i++)

	{

		int cha = data[i] - data[i - 1];

		if (cha >= ha) cha = ha;

		a[i] = a[i - 1] + cha;

		b[a[i]] = 1;

	}

	r = a[m] + ha;

	for (int i = 1; i <= r; i++)

		dp[i] = inf;

}

signed main()

{

	init();

	for (int i = 1; i <= r; i++)

		for (int j = s; j <= t; j++)

		{

			if (i >= j)

			{

				if (b[i]) dp[i] = min(dp[i - j] + 1, dp[i]);//如果该数已被标记，就要加1

				else dp[i] = min(dp[i - j], dp[i]);

			}

		}

	for (int i = a[m]; i <= r; i++)

		ans = min(ans, dp[i]);

	printf("%lld", ans);//输出最小值。

	return 0;

}