每个点有两种转移方式,要么由h+d转移过来,要么由h+1转移过来
#include <bits/stdc++.h> #define int long long int _= 0, Case = 1; using namespace std; #define all(v) begin(v),end(v) #define nline '\n' const int N=5500; int c[N][N]; int f[N][N]; int mmax[N]; void solve(int Case) { int n,h,d; cin>>n>>h>>d; for(int i=1;i<=n;i++){ int cnt; cin>>cnt; for(int j=1;j<=cnt;j++){ int p; cin>>p; c[i][p]++; } } for(int i=h;i>=0;i--){ for(int j=1;j<=n;j++){ f[i][j]=max(f[i+1][j],mmax[i+d])+c[j][i]; mmax[i]=max(mmax[i],f[i][j]); } } cout<<mmax[0]<<nline; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); // cin >> _; for (Case = 1; Case <= _; Case++) solve(Case); return 0; }