题目很好懂,数据量很大,把两个循环合并都能省不少时间!

不过我没试过用普通的数组,估计会超时!

据说用dp+线段树;

嗯,我自己写了一个,确实没那么难!

不过用线段树时,要搞清楚父节点存什么!

在此纪念我的第一道线段树!!!

下面是我的代码:

#include<stdio.h>
#include<memory.h>
#define intt long long
#define max(a,b) (a>b?a:b)
#define min(a,b) (a>b?b:a)
#define MAX 50005
#define loc(a,b) ((a+b)|!(a==b))
intt dp[MAX+MAX];
intt value[MAX];
void update(int s,int e,int l,int r,intt v){
//对于s到e,更新l到r的值,大于v的改成v
if(s==e||dp[loc(s,e)]<=v){
dp[loc(s,e)]=min(v,dp[loc(s,e)]);
return ;
}
int mid=(s+e)/2;
if(l<=mid)//处理左节点
update(s,mid,l,min(r,mid),v);
if(r>=mid+1)//处理右节点
update(mid+1,e,max(mid+1,l),r,v);
dp[loc(s,e)]=min(dp[loc(s,e)],dp[loc(e,e)]);//更新父值
}
int main(){
int n;
while(scanf(“%d”,&n)==1){
int i,t;
memset(dp,’1′,sizeof(dp));//将所有节点赋一个最大值,直接更新
dp[loc(0,0)]=0;
for(i=1;i<=n;i++)
scanf(“%lld”,&value[i]);
for(i=1;i<=n;i++){
scanf(“%d”,&t);
update(1,n,i,min(i+t-1,n),dp[loc(i-1,i-1)]+value[i]);
}
printf(“%lld\n”,dp[loc(1,n)]);
}
return 0;
}

 

发表评论

电子邮件地址不会被公开。

Post Navigation