洛谷P1107 - 雷涛的小猫

 题解 / 洛谷
被浏览

我们根据题意,发现这是一个 DP 题,定义$f_{i,j}$表示在高度为$i$,当前要爬的树为$j$所能获得的最大柿子数。

易得状态转移方程:$f_{i,j}=max(f_{i-1,j},f_{i-delta,k}) (1\leq k \leq n)$ 当$i>delta$时后一项成立。

于是我们得到了一个时间复杂度为$O(H \times N^2)$,空间复杂度为$O(N \times H)$的算法啦。。

然而$N,H=2000$的数据这个时间复杂度还是难以承受,所以需要进一步的优化。

我们发现对于每个$i$,第二个转移的$i-delta$总是固定的,所以就可以直接处理出高度为$i$时$f_{i,j}$的最大值,时间复杂度降到$O(N \times H)$

接下来上代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<cstdio>
#include<iostream>
using namespace std;
#define gc ch=getchar()
inline int read(){
int x=0,f=1;char gc;
for(;ch<'0'||ch>'9';gc)if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';gc)x=x*10+ch-'0';
return x*f;
}
#undef gc
// 以上为快读,听说不用读入优化会TLE,比如cin、cout
int n,h,d,g[2005],a[2005][2005],f[2005][2005];
// g[i]表示高度为i时f[i][j]的最大值
int main(){
n=read();h=read();d=read();
for(int i=1;i<=n;i++){
a[i][0]=read();
for(int j=1;j<=a[i][0];j++)a[i][read()]++;
// 注意,是每个上面有1个,所以要加一,而不是赋值为一
}
for(int i=1;i<=h;i++){
for(int j=1;j<=n;j++)f[i][j]=f[i-1][j]+a[j][i];
if(i>d)for(int j=1;j<=n;j++)f[i][j]=max(f[i][j],g[i-d]+a[j][i]);
for(int j=1;j<=n;j++)g[i]=max(f[i][j],g[i]);
// 转移见上
}
printf("%d",g[h]);
}
 上一页