dp。
刚开始我想的是dp[i][j]表示在第 i 棵树上，高度为h能吃到的最多的果子，如此能得到转移方程: dp[i][j] = max(dp[i][j + 1], dp[k][j + derta]) (k = 1~n && k != i)。但因为这样写会导致dp[k][j + derta] (k > i)的部分没有更新，所以应该把dp试的两胃交换一下。这样dp方程就能正常转移了：
dp[i][j] = max(dp[i + 1][j], max(dp[i + derta][k]) (k = 1~n && k != j) )
然而这样的时间复杂度是O(h * n * n)的，过不了。
优化：观察 max(dp[i + derta][k]) (k = 1~n && k != j),实际上我们就是在高度为i + derta 的所有状态中取一个Max，所以可以开一个数组Max[i]代表高度为 i 时dp[i][j]的最大值，然后每一次求完dp[i][j]时动态更新Max[i]即可。所以转移方程就变成了
dp[i][j] = max(dp[i +1][j], Max[i +derta])
时间复杂度O(h * n)。
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cmath> 5 #include<cstring> 6 #include<cstdlib> 7 #include<stack> 8 #include<queue> 9 #include<vector> 10 #include<cctype> 11 using namespace std; 12 #define space putchar(' ') 13 #define enter puts("") 14 #define Mem(a) memset(a, 0, sizeof(a)) 15 typedef long long ll; 16 typedef double db; 17 const int INF = 0x3f3f3f3f; 18 const db eps = 1e-8; 19 const int max_hig = 2e3 + 5; 20 const int maxn = 5e3 + 5; 21 inline ll read() 22 { 23 ll ans = 0; 24 char ch = getchar(), last = ' '; 25 while(!isdigit(ch)) {last = ch; ch = getchar();} 26 while(isdigit(ch)) {ans = (ans << 3) + (ans << 1) + ch - '0'; ch = getchar();} 27 if(last == '-') ans = -ans; 28 return ans; 29 } 30 inline void write(ll x) 31 { 32 if(x < 0) putchar('-'), x = -x; 33 if(x >= 10) write(x / 10); 34 putchar(x % 10 + '0'); 35 } 36 37 int n, h, d; 38 int a[max_hig][maxn], dp[max_hig][maxn], Max[max_hig]; 39 40 int main() 41 { 42 n = read(), h = read(), d = read(); 43 for(int i = 1; i <= n; ++i) 44 { 45 int x = read(); 46 for(int j = 1; j <= x; ++j) a[read()][i]++; 47 } 48 for(int i = h; i >= 0; --i) 49 for(int j = 1; j <= n; ++j) 50 { 51 dp[i][j] = dp[i + 1][j]; 52 if(i + d <= h) dp[i][j] = max(dp[i][j], Max[i + d]); 53 if(a[i][j]) dp[i][j] += a[i][j]; 54 Max[i] = max(Max[i], dp[i][j]); 55 } 56 int ans = 0; 57 for(int i = 1; i <= n; ++i) ans = max(ans, dp[0][i]); 58 write(ans); enter; 59 return 0; 60 }