自动搬运

查看原文

来自洛谷，原作者为

	issue_is_fw 我又从轮回的尽头回来了呢,泽田纲吉

搬运于2025-08-24 21:21:01，当前版本为作者最后更新于2020-02-26 13:16:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

一、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:要是觉得对你有帮助，评论一下让我知道好嘛...!?