(不知道这玩意是不是叫阶段)
为什么枚举高度的第一层for是从高往低,从低往高程序就不对。
低往高30pts
#include<bits/stdc++.h>
using namespace std;
int n,h,del,a[2005][2005],t,m,dp[2005][2005],ma[2005];
int main()
{
cin>>n>>h>>del;
for(int i=1;i<=n;i++)
{
cin>>m;
for(int j=1;j<=m;j++)
cin>>t,a[i][t]++;
dp[i][0]=a[i][0],ma[i]=max(ma[i],dp[i][t]);
}
for(int j=0;j<=h;j++)
{
for(int i=1;i<=n;i++)
{
dp[i][j]=max(dp[i][j-1],ma[j-del])+a[i][j];
ma[j]=max(ma[j],dp[i][j]);
}
}
// for(int i=1;i<=n;i++)
// {
// for(int j=0;j<=h;j++)
// cout<<ma[j]<<" ";
// cout<<endl;
// }
int maxs=0;
for(int i=1;i<=n;i++)
maxs=max(maxs,dp[i][h]);
cout<<maxs;
return 0;
}
高往低100pts
#include<bits/stdc++.h>
using namespace std;
int n,h,del,a[2005][4005],t,m,dp[2005][4005],ma[4005];
int main()
{
cin>>n>>h>>del;
for(int i=1;i<=n;i++)
{
cin>>m;
for(int j=1;j<=m;j++)
cin>>t,a[i][t]++;
}
for(int j=h;j>=0;j--)
{
for(int i=1;i<=n;i++)
{
dp[i][j]=max(dp[i][j+1],ma[j+del])+a[i][j];
ma[j]=max(ma[j],dp[i][j]);
}
}
// for(int i=1;i<=n;i++)
// {
// for(int j=0;j<=h;j++)
// cout<<dp[i][j]<<" ";
// cout<<endl;
// }
int maxs=0;
for(int i=1;i<=n;i++)
maxs=max(maxs,dp[i][0]);
cout<<maxs;
return 0;
}