AcWing 3073. 雷涛的小猫
原题链接
中等
作者:
炽热的
,
2022-05-29 15:44:56
,
所有人可见
,
阅读 285
动态规划
$f(i, j)$ 表示小猫正在第 $i$ 棵树上的第 $j$ 层时 获得柿子的最大值
状态转移:小猫可以从 树的上一层下来 或者 其他树上跳下来
- 因此 $f(i, j) = max(f(i, j + 1), f(k, j + d)) + w(i, j) $, $1 <= k <= n$
朴素
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2010;
int n, h, d;
int w[N][N];
int f[N][N];
int main()
{
cin >> n >> h >> d;
for (int i = 1; i <= n; i ++ )
{
int cnt;
cin >> cnt;
while (cnt -- )
{
int j;
cin >> j;
w[i][j] ++ ;
}
}
for (int j = h; ~j; j -- )
for (int i = 1; i <= n; i ++ )
{
f[i][j] = f[i][j + 1] + w[i][j];
for (int k = 1; k <= n; k ++ )
f[i][j] = max(f[i][j], f[k][j + d] + w[i][j]);
}
int res = 0;
for (int i = 1; i <= n; i ++ ) res = max(res, f[i][0]);
cout << res;
return 0;
}
上面 $ n^{3} $ 做法必然超时,然后发现第三层循环是找上面层的最大值, 用一个数组记录每层的最大值就可以了
AC 代码
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 4010;
int n, h, d;
int w[N][N];
int f[N][N], g[N];
int main()
{
scanf("%d%d%d", &n, &h, &d);
for (int i = 1; i <= n; i ++ )
{
int cnt;
scanf("%d", &cnt);
while (cnt -- )
{
int j;
scanf("%d", &j);
w[i][j] ++ ;
}
}
for (int j = h; ~j; j -- )
for (int i = 1; i <= n; i ++ )
{
f[i][j] = max(f[i][j + 1], g[j + d]) + w[i][j];
g[j] = max(g[j], f[i][j]);
}
int res = 0;
for (int i = 1; i <= n; i ++ ) res = max(res, f[i][0]);
printf("%d\n", res);
return 0;
}
mobai
niyaoxiewan
haode