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<