To boldly go where no one has gone before.

【学习笔记】路径压缩dp

2019-06-18 13:35:19


例题 P1052

瞟一眼一下这道题,感觉好像是个很简单的$\text{dp}$,只需要用$f[i]$维护在$i$位置需要踩的最少石子数,然后按照$f[i]=\min(f[i-j]\vert i-j\geq0,j\in[s,t])+stone[i]$转移一发即可。

但是仔细一看:$N\leq\text{1e9}$,完蛋。

转移方法肯定是不会改变的,那么肯定需要用某种方式进行离散化(也就是所谓的路径压缩),然后再进行转移。

分析

观察这道题的$s,t\in[1,10]$,然后一想:$lcm(1,2,\cdots,10)=2520$,然后$2520\times100=252000=\text{2e5}$,这好像就变成正常数据范围了。

事实上这是正确的。这里使用的路径压缩就是用$lcm(1,2,\cdots,10)=2520$来对每一段距离取模,从而达到缩短路径的目的。可以简单思考一下, 不管青蛙怎么样跳,它肯定可以跳到$2520$处,合情推理一下,对$2520$取模之后的距离可以表示原距离的所有情况,也就是说是不是一定会踩到石头上只与对$2520$取模之后的余数相关,而与多出去的那一部分无关。这个也不难理解,总可以用某种距离组合来得出压缩之前的情况。

因此,可以大胆地进行路径压缩!具体方式为找到一种能将长距离状态简化为短距离状态的方法,此后再进行$\text{dp}$。

#include<bits/stdc++.h>
using namespace std;
const int LCM = 2520;
const int MAXN = 110;
int l, s, t, m;
int a[MAXN], d[MAXN], f[MAXN * LCM];
bool stone[MAXN * LCM];

int main()
{
    scanf("%d%d%d%d", &l, &s, &t, &m);
    for(int i = 1; i <= m; i++)
        scanf("%d", &a[i]);
    sort(a + 1, a + m + 1);
    for(int i = 1; i <= m; i++)
        d[i] = (a[i] - a[i - 1]) % LCM;
    for(int i = 1; i <= m; i++)
    {
        a[i] = a[i - 1] + d[i];
        stone[a[i]] = true;
    }
    l = a[m];
//  descrete
//  printf("%d\n", l);
    for(int i = 1; i <= l + t; i++)
        f[i] = m;
    f[0] = 0;
    for(int i = 1; i <= l + t; i++)
        for(int j = s; j <= t; j++)
        {
            if(i - j >= 0)
                f[i] = min(f[i], f[i - j]);
            f[i] += stone[i];
        }
    int ans = 0x3f3f3f3f;
//  printf("%d", ans);
    for(int i = l; i < l + t; i++)
        ans = min(ans, f[i]);
    printf("%d", ans);
    return 0;
}