关于这题的阶段
查看原帖
关于这题的阶段
157820
Fur_Zes楼主2024/3/15 20:20

(不知道这玩意是不是叫阶段)

为什么枚举高度的第一层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;
}
2024/3/15 20:20
加载中...