文章目录

C-DongDong跳一跳

https://ac.nowcoder.com/acm/contest/904/C
题意：给n个数，每个数有 杆的高度 和 权值 两种属性，要求从第一个杆上跳，只能从左往右，并且高度差小于等于M，求能获得的最大的权值

有想过dp，dp[x]表示高度为x的时候所获得的最大的权值，就跟背包问题差不多，但是直接这样dp是没有顺序的，而且遍历一次高度，在遍历一次物品，复杂度也过不去啊

题解：所以就是处理第i个物品的时候，使用前i-1更新的dp来维护出当前的这个高度的最大值，然后这个最大值又用来更新出前i个物品弄出的dp

#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=1e6+5;
LL a[maxn],h[maxn];
LL dp[maxn];//dp[x]表示高度为x时能获得的最大值 
int main()
{
	int N,M;
	while(cin>>N>>M)
	{
		LL maxH=0,res=0;
		for(int i=1;i<=N;i++)
		{
			scanf("%lld%lld",h+i,a+i);
			maxH=max(maxH,h[i]);
		}
		for(int i=1;i<=N;i++)
		{
			LL tp=a[i];
			for(int x=max(1LL,h[i]-M);x<=min(maxH,h[i]+M);x++)//高度的绝对值小于等于M 
			{
				tp=max(tp,dp[x]+a[i]);//用前i-1个物品更新出的dp来维护出当前高度的最大值 
			}
			dp[h[i]]=max(dp[h[i]],tp);//dp更新到第i个 
			res=max(res,tp);
		}
		cout<<res<<endl;
	}
}