【洛谷】P1107 [BJWC2008]雷涛的小猫

2023-12-21 21:34:58

1.题意

给出若干棵树，以及每棵树不同高度有几个柿子的信息。以及给出走法规则，求能够获取到最多的柿子数。

2.分析

线形dp题
问题抽象转换

2.1 方法1

我自己的方法是：设 dp[i][j] 表示第j棵树，高度为i时获得的最大值。然后三重循环遍历一下，第三重循环的含义是从之前较高的树上找出一个最大的值（一个最优解）。代码如下：

 //dp计算
for(int i = h-delta;i>0;i--){//i为高度
    for(int j = 1;j<=n;j++){//j为树的下标
        dp[i][j] = dp[i+1][j];//继承
        for(int k = 1;k<=n;k++) { //找中间跳一次
            dp[i][j] = max(dp[i][j], dp[i + delta][k]);
        }
        dp[i][j] += fruit[j][i]; //加上当前的果子
    }
}

但是这个代码会让你 TLE，该如何简化呢？可以看到这里的最外层的for循环其实是高度从高到低，也就是说：较高层的最大值其实在除了第一次做j的循环时需要寻找，以后循环j的时候便不用再循环了，而是直接可以利用上一次找出的最大值，这个最大值放到rec[]中。rec[i]就表示高度为i时能够得到最大值。修改后的代码如下3示。

2.2方法2

这是洛谷的大佬给出的想法：
将每棵树的每个高度看成是一个图的节点，然后进行一波图节点的转移操作，最后得到一个最优解。这里的思想贵在抽象，能够将所学的知识应用到实际的问题上！

3.代码

// Created by lawson on 20-6-17.
#include<iostream>
#include<cstdio>
using namespace std;

const int maxN = 2005;
int dp[maxN][maxN];//dp[i][j]表示第j棵树，高度为i时获得的最大值
int fruit[maxN][maxN];//fruit[i][j]表示第i棵树，高度为j时有柿子
int rec[maxN];//rec[i]用于记录高度为i时的最大值

int n,h,delta;
int main(){
    scanf("%d%d%d",&n,&h,&delta);
    for(int i = 1;i<= n;i++){//树的下标
        int num,loc;//柿子数； 每个柿子所在的高度
        scanf("%d",&num);
        for(int j = 1;j<=num;j++)//柿子个数
        {
            scanf("%d",&loc);
            fruit[i][loc] ++;//高度为loc,第i棵树时有一个柿子
        }
    }

    for(int i = h;i>h-delta;i--){//高度为i
        for(int j = 1;j<=n;j++){//树的下标为j
            dp[i][j] = fruit[j][i] + dp[i+1][j]; //本高度+上面高度继承
        }
    }

    //dp计算
    for(int i = h-delta;i>0;i--){//i为高度
        for(int j = 1;j<=n;j++){//j为树的下标
            dp[i][j] = dp[i+1][j];//继承
            if(rec[i+delta]){ //如果之前高度为 i+delta 时的最大值已经找到过了
                dp[i][j] = max(dp[i][j],rec[i+delta]);
            }
            else{//没有记录，第一次需要寻找
                for(int k = 1;k<=n;k++) { //找中间跳一次
                    dp[i][j] = max(dp[i][j], dp[i + delta][k]);
                }
                rec[i+delta] = dp[i][j];
            }
            dp[i][j] += fruit[j][i]; //加上当前的果子
        }
    }
    int res = 0;
    for(int i = 1;i<= n;i++)
        res = max(res,dp[1][i]);
    printf("%d\n",res);
}

4.测试用例

3 10 2
3 1 4 10
6 3 5 9 7 8 9
5 4 5 3 6 9

01.如何降维？

码农公寓