本文共 2304 字，大约阅读时间需要 7 分钟。

1.因为一点小失误，一直没调出来，有点可惜

2.实际上有点LIS的感觉，我们设$d(i)$表示从$i$开始的攻击力最大值，$b[i]$为位置$i$的攻击力，那么可以得出：

$d(i)=max(d(i),b[i]+d(j)),j>i$

考虑从后向前递推，那么我们只需要求出每一个位置前面已经更新的位置中，满足生命值之差的绝对值小于等于$d$的最大攻击力转移

考虑使用线段树维护，下标的含义是生命值，树的权值为最大攻击力，那么每次只需求出区间$[max(a[i]-d,1),a[i]+d)$中的最值，然后更新生命值$a[i]$的权值。只需单点修改和区间查询的最值线段树

因为$a[i]+d\le 2e^5$，因此我们要在这个最大范围内建树维护

PS：本题从前向后和从后向前递推均可以

#include <set>#include <map>#include <stack>#include <queue>#include <math.h>#include <cstdio>#include <string>#include <bitset>#include <cstring>#include <sstream>#include <iostream>#include <unordered_map>using namespace std;#define fi first#define se second#define pb push_back#define ins insert#define lowbit(x) (x&(-x))#define mkp(x,y) make_pair(x,y)#define mem(a,x) memset(a,x,sizeof a);typedef long long ll;typedef long double ld;typedef unsigned long long ull;typedef pair<int,int> P;const double eps=1e-8;const double pi=acos(-1.0);const int inf=0x3f3f3f3f;const ll INF=1e18;const int Mod=1e9+7;const int maxn=2e5+10;int a[maxn],b[maxn];ll dp[maxn];ll tree[maxn<<2];inline ll max(int a,int b){       return a>b?a:b;}void build(int i,int l,int r){       if(l==r){           tree[i]=0;        return;    }    int mid=(l+r)>>1;    int k=i<<1;    build(k,l,mid);    build(k|1,mid+1,r);    tree[i]=max(tree[k],tree[k|1]);}void update(int i,int l,int r,int x,ll y){       if(l==r){   	    tree[i]=y;	    return;	}	int mid=(l+r)>>1;	int k=i<<1;	if(x<=mid) update(k,l,mid,x,y);	else update(k|1,mid+1,r,x,y);	tree[i]=max(tree[k],tree[k|1]);}ll query(int i,int l,int r,int x,int y){       if(x<=l && y>=r) return tree[i];    int mid=(l+r)>>1;    int k=i<<1;	if(y<=mid) return query(k,l,mid,x,y);	else if(x>mid) return query(k|1,mid+1,r,x,y);	return max(query(k,l,mid,x,y),query(k|1,mid+1,r,x,y));}int main(){       int n,d;    cin>>n>>d;    build(1,1,maxn-10);    ll res=0;    for(int i=1;i<=n;i++)        cin>>a[i]>>b[i];    for(int i=n;i>=1;i--){           int l=max(1,a[i]-d),r=a[i]+d;        dp[i]=query(1,1,maxn-10,l,r)+b[i];        res=max(res,dp[i]);        update(1,1,maxn-10,a[i],dp[i]);    }    cout<<res<<endl;    return 0;}

转载地址：http://guqq.baihongyu.com/