ZOJ 3632 Watermelon Full of Water (线段树区间更新 + dp)

题目大意：

让每天都能吃到西瓜。最少需要花多少钱。

思路分析：

dp[pos] 就表示要让前i天每天都有西瓜吃，最少需要花多少钱。

那么如果你买这个西瓜的话。那么这个西瓜能吃的持续时间都要更新一下。

然后再在每个西瓜的更新部分取最小的，就可以是这个点所能得到的最小值。

其实就是 dp[i] = min (dp[i] , dp[ j - k +1] + a[j]);

但是枚举前面的时候会超时，就用线段树维护。

5
1 2 3 4 5
1 2 2 2 2

给出这组数据是说，每次买西瓜的时候，都要和前一次的大小做比较，来表示西瓜在这里刚好吃完。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define maxn 55555 #define lson num<<1,s,mid #define rson num<<1|1,mid+1,e #define inf ((1LL)<<60) typedef long long LL; using namespace std; LL dp[maxn<<2]; void pushdown(int num) { if(dp[num]!=inf) { dp[num<<1]=min(dp[num<<1],dp[num]); dp[num<<1|1]=min(dp[num<<1|1],dp[num]); dp[num]=inf; } } void build(int num,int s,int e) { dp[num]=inf; if(s==e) { return; } int mid=(s+e)>>1; build(lson); build(rson); } void update(int num,int s,int e,int l,int r,LL val) { if(l<=s && r>=e) { dp[num]=min(val,dp[num]); return; } pushdown(num); int mid=(s+e)>>1; if(l<=mid)update(lson,l,r,val); if(r>mid)update(rson,l,r,val); } LL query(int num,int s,int e,int pos) { if(s==e) { return dp[num]; } pushdown(num); int mid=(s+e)>>1; if(pos<=mid)return query(lson,pos); else return query(rson,pos); } int cost[maxn]; int last[maxn]; int main() { int n; while(cin>>n) { for(int i=1;i<=n;i++)cin>>cost[i]; for(int i=1;i<=n;i++)cin>>last[i]; build(1,1,n); int pos=last[1]; if(pos>n)pos=n; update(1,1,n,1,pos,(LL)cost[1]); for(int i=2;i<=n;i++) { LL cur=min(query(1,1,n,i),query(1,1,n,i-1)); pos=i+last[i]-1; if(pos>n)pos=n; update(1,1,n,i,pos,cur+(LL)cost[i]); } cout<

ZOJ 3632 Watermelon Full of Water (线段树 区间更新 + dp)