ZOJ3381
dp[i]는 i에서 시작하는 최대 수익을 기록합니다.
dp[i]=s[i]+max(dp[x]|i+x[i]<=x세그먼트 트리를 이용해서 최대치를 유지하면 돼요.
#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&&l==pos)
{
seg[i]=x;
return;
}
int mid=(l+r)>>1;
if(mid>=pos)
ud(l,mid,pos,2*i,x);
else
ud(mid+1,r,pos,2*i+1,x);
up(i);
}
int qu(int l,int r,int a,int b,int i)
{
if(l==a&&r==b)
return seg[i];
int mid=(l+r)>>1;
if(mid>=b)
return qu(l,mid,a,b,2*i);
else
if(a>mid)
return qu(mid+1,r,a,b,2*i+1);
else
return max(qu(l,mid,a,mid,2*i),qu(mid+1,r,mid+1,b,2*i+1));
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
build(1,n,1);
for(int i=1;i<=n;i++)
scanf("%d%d%d",s+i,x+i,y+i);
dp[n]=s[n];
for(int i=n-1;i>=1;i--)
{
ud(1,n,i+1,1,dp[i+1]);
if(i+y[i]-1<=n)
dp[i]=s[i]+qu(1,n,i+x[i],i+y[i]-1,1);
else
if(i+x[i]<=n)
dp[i]=s[i]+qu(1,n,i+x[i],n,1);
else
dp[i]=s[i];
}
printf("%d
",dp[1]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
flex 그래프 이벤트 데이터 가져오기우선 몇 개의 가방을 도입해야 합니다. import mx.charts.events.ChartItemEvent; import mx.charts.series.items.ColumnSeriesItem; pri...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.