问题标题: 关于小学组市赛T4的正确解法

这一题其实还是很好理解的，一看就是一个线**dp。

所以，我们就有了一个初级代码（别问我为什么不解释）

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1000000+10;
int n;
LL a[N],b[N];
LL f[N];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld%lld",&a[i],&b[i]);
	for(int i=1;i<=n;i++){
		f[i]+=a[i];
		if(i+b[i]+1<=n)
			for(int j=i+b[i]+1;j<=n;j++)
				f[j]=max(f[j],f[i]);
	}
	LL ans=0;
	for(int i=1;i<=n;i++)
		ans=max(ans,f[i]);
	printf("%lld\n",ans);
	return 0;
}

这显然超时了，毕竟O（n^2）的时间复杂度。

但是我是一个懒人，于是，我就想不改dp的主体，只是优化 i+b[i]+1~n 这段的修改。

于是，一个简单的dp套线段树的AC写法就出现了：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1000000+10;
int n;
LL a[N],b[N];
LL f[N],Change[N<<2];
void Down(int p){
	if(Change[p]!=-1){
		Change[p<<1]=max(Change[p<<1],Change[p]);
		Change[p<<1|1]=max(Change[p<<1|1],Change[p]);
		Change[p]=-1;
	}
}
void Add(int p,int l,int r,int x,LL v){
	if(x<l||x>r)return;
	if(l==r){
		if(Change[p]!=-1)
			f[l]=max(f[l],Change[p]);
		f[l]+=v;
		Change[p]=-1;
		return;
	}
	Down(p);
	int mid=(l+r)>>1;
	Add(p<<1,l,mid,x,v);
	Add(p<<1|1,mid+1,r,x,v);
}
void Update(int p,int l,int r,int x,int y,LL v){
	if(x>r||y<l)return;
	if(x<=l&&r<=y){
		Change[p]=max(Change[p],v);
		return;
	}
	Down(p);
	int mid=(l+r)>>1;
	Update(p<<1,l,mid,x,y,v);
	Update(p<<1|1,mid+1,r,x,y,v);
}
LL Query(int p,int l,int r,int x){
	if(l==r)return f[l];
	Down(p);
	int mid=(l+r)>>1;
	if(x<=mid)return Query(p<<1,l,mid,x);
	else return Query(p<<1|1,mid+1,r,x);
}
int main(){
	memset(Change,-1,sizeof(Change));
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld%lld",&a[i],&b[i]);
	for(int i=1;i<=n;i++){
		Add(1,1,n,i,a[i]);
		int tmp=Query(1,1,n,i);
		if(i+b[i]+1<=n)
			Update(1,1,n,i+b[i]+1,n,tmp);
	}
	LL ans=0;
	for(int i=1;i<=n;i++)
		ans=max(ans,Query(1,1,n,i));
	printf("%lld\n",ans);
	return 0;
}

代码是真的 丑，别骂

杜承俊在2023-03-20 23:40:59追加了内容

我只是表达自己的观点啊，普通的递归其实更简单，我就是玩一玩，嘿嘿嘿

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1000000+10;
int n;
LL a[N],b[N];
LL f[N];
LL DFS(int cur){
	if(f[cur]!=-1)return f[cur];
	if(cur>n)return 0;
	LL ans=0;
	ans=max(DFS(cur+1),DFS(cur+b[cur]+1)+a[cur]);
	return f[cur]=ans;
}
int main(){
	memset(f,-1,sizeof(f));
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&a[i],&b[i]);
	printf("%lld\n",DFS(1));
	return 0;
}