luogu2948 滑雪课

题解里面全是dp的大神本蒟蒻瑟瑟发抖奉上一篇记忆化搜索...

其实嘛，记忆化搜索还是很安全透彻清真人品的，一般递推不好实现dp可以用记忆化搜索

然后本题先预处理一个mint[i]代表当前能力值为i，参与滑雪的最小时间。一开始赋初值为\(+\infty\)，每当读入一个滑雪任务(c,d)后，把[c,100]区间内的数组对d去取一个min

然后就可以缩索了，search(x,y)返回当前时间为x，能力值为y滑雪最大次数。枚举所有课程，如果这个课程开始时间在x后面(或者就在x也就是\(\ge x\)，那么我们就用上这门课来更新本次答案，也就是search(a[i].m + a[i].l, a[i].a)。mla如题意。一个剪枝：当当前课程a小于等于当前能力值，选他一定不比不选他优，所以不用考虑。然后贪心地在当前时间x和课程开始时间内滑雪(用当前时间除以当前能力值能滑雪最短时间就是最大滑雪的次数)。

备注：数据貌似有一点水，不写记忆化tle两个点，不写记忆化开O2tle一个点。

#include <cstdio>

#include <iostream>

#include <cstring>

using namespace std;

struct course

{

    int m, l, a;

}a[110];

int mint[110];

int t, s, n, f[10010][110];

//记忆化缩索，表示在x时候能力值为y能滑雪最大数

int search(int x, int y)

{

    if(f[x][y] != -1)

        return f[x][y];

    f[x][y] = 0;

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

        if(a[i].m >= x && a[i].a > y)

            f[x][y] = max(f[x][y], search(a[i].m + a[i].l, a[i].a) + (a[i].m - x) / mint[y]);

    return f[x][y];

}

int main()

{

    scanf("%d%d%d", &t, &s, &n);

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

    {

        scanf("%d%d%d", &a[i].m, &a[i].l, &a[i].a);

    }

    a[s + 1] = (course){t, 0, 101};

    memset(mint, 0x3f, sizeof(mint));

    for (int c, d, i = 1; i <= n; i++)

    {

        scanf("%d%d", &c, &d);

        for (int j = c; j <= 100; j++)

            mint[j] = min(mint[j], d);

    }

    memset(f, -1, sizeof(f));

    printf("%d\n", search(0, 1));

    return 0;

}

让我们一起膜拜大佬林瑞堂 @olinr

让我们一起膜拜搜索王@ZAGER

巴特西

luogu2948 滑雪课

最新文章

热门文章