dp+线段树;
dp[i] = s[i] + max{dp[i + j] | x[i] ≤ j < y[i]}
用线段数维护max。
#include<iostream>
using namespace std;
const int N=50000;
struct node
{
int left,right;
int ma;
};
struct point
{
int si,xi,yi;
};
point p[N+10];
node seg[N*3];
int dp[N+10];
int n;
inline int max(int a,int b)
{
return a>b?a:b;
}
void init(int l,int r,int c)
{
seg[c].left=l;
seg[c].right=r;
seg[c].ma=0;
if(l==r)
return;
int mid=(l+r)>>1;
init(l,mid,c*2);
init(mid+1,r,c*2+1);
}
int qurey(int l,int r,int c)
{
if(seg[c].left>=l&&seg[c].right<=r)
return seg[c].ma;
int mid=(seg[c].left+seg[c].right)>>1;
if(r<=mid)
return qurey(l,r,c*2);
else if(l>mid)
return qurey(l,r,c*2+1);
else
return max(qurey(l,mid,c*2),qurey(mid+1,r,c*2+1));
}
void update(int pos,int num,int c)
{
if(seg[c].left==seg[c].right)
{
seg[c].ma=max(seg[c].ma,num);
return ;
}
int mid=(seg[c].left+seg[c].right)>>1;
if(pos<=mid)
update(pos,num,c*2);
else
update(pos,num,c*2+1);
seg[c].ma=max(seg[c*2].ma,seg[c*2+1].ma);
}
int main()
{
int i,j;
while(scanf("%d",&n)!=EOF)
{
int l,r;
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
scanf("%d%d%d",&p[i].si,&p[i].xi,&p[i].yi);
init(1,n,1);
for(i=n;i>0;i--)
{
dp[i]=p[i].si;
l=i+p[i].xi;
r=i+p[i].yi-1;
if(l>n)
{
update(i,dp[i],1);
continue;
}
if(r>n)
r=n;
dp[i]+=qurey(l,r,1);
update(i,dp[i],1);
}
printf("%d/n",dp[1]);
}
return 0;
}