洛谷 1052 dp 状态压缩

时间：2021-08-15 08:27:50

#洛谷1052 dp 状态压缩

传送门

(https://www.luogu.org/problem/show?pid=1052#sub)

做完这道题之后，感觉涨了好多见识，以前做的好多状压题目都是将一维压成一个数，一直感觉状压本质就是位运算来保存状态，这道题给了一个全新的思路，通过裁剪无用的状态来有效的减少状态量，从而使空间和时间达到要求

初看题目感觉还是挺简单的，但是1e9的使得线性dp无论空间还是时间都难以接受，考虑如何减少状态量

发现题目中石子的数量只有100个，而且每次跳跃的距离小于10，可见实际上桥上的石子排列应该非常稀疏，尝试从此处优化

不难发现如果两个石子之间的距离大于一定值时，它们的距离就将失去意义，

洛谷 1052 dp 状态压缩

比如每次跳跃距离在(5,7),而某两个石子的距离为10000，那么将他们的距离调整为5000对结果无任何影响

优化距离之后直接进行dp转移即可，笔者选择了2 * t作为优化距离的分界线

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

Warning：

  • 对a数组进行修改操作时，不能对原数组进行修改，例如，a[1] = 1, a[2] = 300 , a[3] = 301，如果在原数组上进行修改，会导致a[2] 被修改为一个较小值，而a[3]此时也会符合修改条件，导致错解

  • 初始化时要注意初始化的值，如果初始化值过大可能导致爆int上限

  • 压缩时可能发生冲突，尤其是在s, t相对接近时，可以适当加大mod的值，同时在压缩两个较远点时适当增加压缩后的距离



#include <cstdio>

#include <algorithm>

#include <cstring>

int l, m, s, t;

const int maxn = 1000000 + 500;

int dp[maxn];

int a[maxn];

int d[maxn];

int cur[maxn];

int mod;

int main () {

    freopen("river.in", "r", stdin);

    freopen("river.out", "w", stdout);

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

    for (int i = 1; i <= m; i++) scanf("%d", &a[i]);

    mod = 2 * t;

    std :: sort(&a[1], &a[m + 1]);

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

        if (a[i] - a[i-1] <= mod) {

            d[i] = a[i] - a[i-1];

        } else {

            d[i] = (a[i] - a[i-1]) % mod + mod;

        }

    }

    // for (int i = 1; i <= m; i++) printf("%d ", a[i]);

    // printf("\n");

    int nowSum = 0;

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

        nowSum += d[i];

        cur[nowSum] = 1;

    }

    for (int i = 0; i <= maxn; i++) dp[i] = 1000000000;

    if (l - nowSum > mod)

        l = nowSum + mod + (l - nowSum) % mod;

    dp[0] = 0;

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

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

            dp[i+j] = std :: min(dp[i+j], dp[i] + cur[i+j]);

        }

    int ans = 0x7fffffff;

    for (int j = l; j <= l + 2 * t; j++)

        ans = std :: min(ans, dp[j]);

    printf("%d", ans);

    return 0;

}

相关文章