for (int j = 1; j <= n; j++) { if (i > delta)//如果目前高度大于可以跳跃上(下)降的长度 { dp[i][j] = max(dp[i - 1][j], max_v[i-delta]) + M[i][j];//当前高度的最大值,从跳跃之前的最大值和不跳跃上升的值比较 } else { dp[i][j] = dp[i - 1][j] + M[i][j];//无法进行跳跃上升的目前最大高度 } max_v[i] = max(max_v[i], dp[i][j]);//存储当前层最大高度 } } cout << max_v[h]; }
P1107 [BJWC2008]雷涛的小猫|解题方案
#include <bits/stdc++.h>
using namespace std;
//萌新小白第一次写题解,请多多包涵
int M[2001][2001];//存储数组
int dp[2001][2001];//dp数组
int max_v[2001];//存放当前高度的最大值
int main()
{
//关闭同步以提高速度
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int n, h, delta;
cin >> n >> h >> delta;
//读入
for (int i = 1; i <= n; i++)
{
int m;
cin >> m;
for (int j = 0; j < m; j++)
{
int H_d;
cin >> H_d;
M[H_d][i]++;
}
}
//重点 i 为高度值, j 为第几个树
for (int i = 1; i <= h; i++)
{
for (int j = 1; j <= n; j++) { if (i > delta)//如果目前高度大于可以跳跃上(下)降的长度 { dp[i][j] = max(dp[i - 1][j], max_v[i-delta]) + M[i][j];//当前高度的最大值,从跳跃之前的最大值和不跳跃上升的值比较 } else { dp[i][j] = dp[i - 1][j] + M[i][j];//无法进行跳跃上升的目前最大高度 } max_v[i] = max(max_v[i], dp[i][j]);//存储当前层最大高度 } } cout << max_v[h]; }
for (int j = 1; j <= n; j++) { if (i > delta)//如果目前高度大于可以跳跃上(下)降的长度 { dp[i][j] = max(dp[i - 1][j], max_v[i-delta]) + M[i][j];//当前高度的最大值,从跳跃之前的最大值和不跳跃上升的值比较 } else { dp[i][j] = dp[i - 1][j] + M[i][j];//无法进行跳跃上升的目前最大高度 } max_v[i] = max(max_v[i], dp[i][j]);//存储当前层最大高度 } } cout << max_v[h]; }