- #include<bits/stdc++.h>
- using namespace std;
- int N, H, Delta;
- int t[2020][2020];//t为原始生成的图,同时也作为保存状态的二维数组
- int dp[2020];//dp[i]表示高度为i时取得的最大价值
- inline void input(){//输入数据并存为图,存图方式如上图图片
- scanf("%d%d%d", &N, &H, &Delta);
- for(register int i = 1; i <= N; i ++){
- int num;
- scanf("%d", &num);
- for(register int j = 1; j <= num; j ++){
- int temp;
- scanf("%d", &temp);
- t[temp][i]++;
- }
- }
- }
- int main(){
- input();
- for(register int i = 1; i <= H; i ++){
- for(register int j = 1; j <= N; j ++){
- if(i <= Delta){//当高度比Delta小时,当前状态只能从同一列的上一个状态转移
- t[i][j] += t[i - 1][j];//
- dp[i] = max(dp[i], t[i][j]);//当前高度能取得的最大价值为当前行所有状态的最大值
- continue;
- }
- t[i][j] += max(dp[i - Delta], t[i - 1][j]);//普通的状态转移方程
- dp[i] = max(dp[i], t[i][j]);//同时要更新当前高度能取得的最大价值
- }
- }
- printf("%d\n", dp[H]);
- return 0;
- }