10pts,dp求调
查看原帖
10pts,dp求调
776582
jhdrgfj楼主2023/2/12 10:52
/*
dp[i][j]表示高度为i,在第j棵树上吃到的柿子数量。 
则状态转移方程为
dp[i][j]=dp[i-1][j]+a[i][j] (i<=delta)
dp[i][j]=max(ma,dp[i-1][j])+a[i][j] (i>delta)
dp边界为dp[1][j]=a[1][j]
*/
#include<bits/stdc++.h>
using namespace std;
int dp[2005][2005],n,h,d;
int a[2005][2005];
int main()
{
	cin>>n>>h>>d;
	int x,y;
	for (int i=1;i<=n;i++){
		scanf("%d",&x);
		for (int j=1;j<=x;j++){
			scanf("%d",&y);
			a[y][i]++;	
		}	
	}
	for (int i=1;i<=n;i++){  //边界
		dp[i][1]=a[i][1];
	}
	int ma=0;
	for (int i=2;i<=h;i++){
		if (i>d){
			for (int j=1;j<=n;j++){
				ma=max(dp[i-d][j],ma);
			}
		}
		for (int j=1;j<=n;j++){
			if (i<=d){
				dp[i][j]=dp[i-1][j]+a[i][j];
			}else{
				dp[i][j]=max(ma,dp[i-1][j])+a[i][j];
			}
		}
	}
	/*
	for (int i=h;i>0;i--){
		for (int j=1;j<=n;j++)
			cout<<a[i][j]<<" ";
		cout<<endl;
	}
	*/
	for (int i=1;i<=n;i++){
		ma=max(dp[h][i],ma);
	}
	cout<<ma;
}

样例能过,但不知道为啥WA了九个点。

2023/2/12 10:52
加载中...