ZOJ 3632 Watermelon Full of Water（dp+线段树 单点修改）

题意：

       一共有n天

        每天西瓜售价为dp[i]元

        该天的西瓜能吃v[i]天 而且这天如果买了西瓜之前的西瓜就要扔掉

        问每天都吃到西瓜的最小花费是多少

思路：

       从最后一天开始dp最小花费

       并用线段树单点更新来维护

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
#define ll long long
#define INF 1e10
ll dp[50000+100];//从后往前 dp[i]必买西瓜的最小花费
int v[50000+100];
ll sum[200000+100];
int n;
void push(int rt)
{
    sum[rt]=min(sum[rt<<1],sum[rt<<1|1]);
}
void build(int l,int r,int rt)
{
    sum[rt]=INF;
    if(l==r)
    {
       return ;
    }
    int m=(l+r)>>1;
    build(l,m,rt<<1);
    build(m+1,r,rt<<1|1);
    push(rt);
}
void update(int key,ll add,int l,int r,int rt)
{
    if(l==r)
    {
        sum[rt]=min(sum[rt],add);
        return ;
    }
    int m=(l+r)>>1;
    if(key<=m) update(key,add,l,m,rt<<1);
    else update(key,add,m+1,r,rt<<1|1);
    push(rt);
}
ll query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        return sum[rt];
    }
    ll res1=INF,res2=INF;
    int m=(l+r)>>1;
    if(L<=m)
    {
        res1=query(L,R,l,m,rt<<1);
    }
    if(R>m)
    {
        res2=query(L,R,m+1,r,rt<<1|1);
    }
    return min(res1,res2);
}
int main()
{
    int i,j,k;
    while(scanf("%d",&n)!=EOF)
    {
        build(1,n+1,1);
        for(i=1;i<=n;i++)
        {
            scanf("%lld",&dp[i]);
        }
        for(i=1;i<=n;i++)
        {
            scanf("%d",&v[i]);
        }
        dp[n+1]=0;
        update(n+1,dp[n+1],1,n+1,1);
        for(i=n;i>=1;i--)
        {
            int r=i+v[i];
            if(r>n+1) r=n+1;
            ll next=query(i+1,r,1,n+1,1);
            dp[i]+=next;
            update(i,dp[i],1,n+1,1);
        }
        
        printf("%lld
",dp[1]);
    }
    return 0;
}