洛谷P1052 过河

洛谷P1052 过河

题意：

题意很明了，就不赘述了（其实是我语文水平有限还很懒… ）

分析:

dp很好想，状态转移方程也简单： $dp\left[i\right]=min\left(dp\right[i],dp[i-j]+mark[i\left]\right);$dp[i]=min(dp[i],dp[i−j]+mark[i]);
然而这个L的范围…都不用说TLE了，连数组都开不了好吧
所以这道题重点并不是dp，而是路径压缩
让我们再看看输入数据的范围：
$1\le L\le 10^9$1≤L≤109
$1\le S\le T\le 10$1≤S≤T≤10
$1\le M\le 100$1≤M≤100
你会发现虽然L的范围很大，S，T和M的范围却都比较小
在一条很长的数轴上仅仅有稀疏的M个点，所以很多空白区域的状态是不用考虑的
先预处理出S和T所有取值的最小公倍数即1~10的最小公倍数2520
当两个石头之间的距离大于2520时对2520取模即可
消去大量多余状态之后你会发现空间复杂度已经降到1e6了，可以开始愉快的写DP了

代码：

#include <bits/stdc++.h>
using namespace std;
int l;
int s, t, m;
int pos[110];
int dp[2520 * 110];
int mark[2520 * 110] = {0}; //用来标记有石头的点
int main(int argc, char const *argv[])
{
    // freopen("input.txt", "r", stdin);
    // freopen("output1.txt", "w", stdout);
    scanf("%d", &l);
    scanf("%d%d%d", &s, &t, &m);
    memset(dp, 0x3f3f3f3f, sizeof dp);

    for (int i = 1; i <= m; ++i)
        scanf("%d", &pos[i]);
    sort(pos + 1, pos + 1 + m);
    int _pos[110];
    _pos[1] = pos[1] > 2520 ? pos[1] % 10 : pos[1];
    mark[_pos[1]] = 1;
    for (int i = 2; i <= m; ++i)
    {
        if (pos[i] - pos[i - 1] > 2520)
            _pos[i] = _pos[i - 1] + (pos[i] - pos[i - 1]) % 2520;
        else
            _pos[i] = _pos[i - 1] + pos[i] - pos[i - 1];
        mark[_pos[i]] = 1;
    }
    int ll = _pos[m] + 2520;

    dp[0] = 0;
    for (int i = 1; i <= ll; ++i)
    {
        for (int j = s; j <= t; ++j)
        {
            if (i < j)
                break;
            dp[i] = min(dp[i], dp[i - j] + mark[i]);
        }
        // printf("mark[%d]=%d dp[%d]=%d\n", i, mark[i], i, dp[i]);
    }

    int ans = 0x3f3f3f3f;
    for (int i = _pos[m]; i <= ll; ++i)
        ans = min(ans, dp[i]);
    printf("%d\n", ans);
    return 0;
}