题解 P1107 【[BJWC2008]雷涛的小猫】

· · 题解

这是你的福利题解，请签收>-<~

一、n^3方做法

1、根据问什么设什么的思想，我们很容易看出，题目中的状态有当前在那颗树，当前的高度。
那我们不妨设dp[i][j]为在i颗树高度为j时的最大吃苹果数。

2、我们发现，当处于第i棵树高度为j时，可以从第i棵树高度为j+1的地方掉下来，
即dp[i][j]=a[i][j]+dp[i][j+1];其中a数组表示第i棵树j位置有几个苹果。

也可以从其他任意一棵树的j+delta跳到第i棵树的j位置，所以我们应该枚举每一颗树，
dp[i][j]=max(dp[i][j],dp[q][j+delta]+a[i][j]);
3、这么一来就很明了了。第一重循环时枚举高度，从h往0递推，
第二重循环枚举当前处于哪一棵树，第三重枚举从哪一棵树转移而来，具体见代码。
#include <bits/stdc++.h>
using namespace std;
int n,h,de;
int a[5009][2009],dp[5009][2009];
int main()
{
    cin>>n>>h>>de;
    for(int i=1;i<=n;i++)
    {
        int t,zz;
        scanf("%d",&t);
        while(t--){
            scanf("%d",&zz);
            a[i][zz]++;
        }
    }
    int maxn=0;
    for(int j=h;j>=0;j--)
    {
        for(int i=1;i<=n;i++)
        {
            dp[i][j]=max(dp[i][j],a[i][j]+dp[i][j+1]);
            for(int q=1;q<=n;q++)
            {
                if(q!=i)
                    dp[i][j]=max(dp[i][j],dp[q][j+delta]+a[i][j]);
            }
            maxn=max(maxn,dp[i][j]);
        }
    }
    cout<<maxn;
}

但是聪明的你肯定发现了，妥妥的tle.

于是有了n^2的优化。

我们想一下，为什么要有第三重循环？我们只不过想从当前高度的状态里挑一棵最大收益的树转移过来。那这样就简单了，我们开一个pre数组保存对应高度的最大收益，转移的时候直接拿过来用就好了。

不懂的话请看代码，很容易理解。

#include <bits/stdc++.h>
using namespace std;
int n,h,de;
int a[5009][2009]，dp[5009][2009]，pre[5009];
int main()
{
    cin>>n>>h>>de;
    for(int i=1;i<=n;i++)
    {
        int t,zz;
        scanf("%d",&t);
        while(t--){
            scanf("%d",&zz);
            a[i][zz]++;
        }
    }
    int maxn=0;
    for(int j=h;j>=0;j--)
    {
        for(int i=1;i<=n;i++)
        {
            dp[i][j]=a[i][j]+dp[i][j+1];//先继承上一次 
            dp[i][j]=max(dp[i][j],pre[j+de]+a[i][j]);//转移 
            pre[j]=max(pre[j],dp[i][j]);//尝试更新当前的pre 
            maxn=max(maxn,dp[i][j]);
        }
    }
    cout<<maxn;
}

希望管理大大能过。第一次写题解被退回来了，原因是排版不整齐。 没有备份，希望这次能过。

ps:要是觉得对你有帮助，评论一下让我知道好嘛...!?