DP+线段树,
dp[i]记录从i开始的最大收益,
dp[i]=s[i]+max(dp[x]|i+x[i]<=x<i+y[i]);
利用线段树维护个最大值就行了
#include<cstdio>
#define MAXN 50010
#define max(a,b) ((a)>(b))?(a):(b)
int n,s[MAXN],x[MAXN],y[MAXN];
int seg[4*MAXN];
int dp[MAXN];
void up(int x)
{
seg[x]=max(seg[2*x],seg[2*x+1]);
}
void build(int l,int r,int i)
{
seg[i]=0;
if(l==r)
return;
int m=(l+r)>>1;
build(l,m,2*i);
build(m+1,r,2*i+1);
}
void ud(int l,int r,int pos,int i,int x)
{
if(l==r&......
阅读全文