2011-0056

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

这道题的意思是告诉你每天的西瓜要多少钱，以及这个西瓜可以吃几天，然后问你怎么买，可以每天吃西瓜且花钱最少。
因为买了一个新的西瓜，之前的西瓜无论有没有吃完，都没用了，所以购买策略应该是从前往后进行。
我们用f[i]表示，前i天能够吃到西瓜，需要多少钱。记a[i],b[i]表示第i天的西瓜的价格和可以吃的天数，接下来我们来思考状态转移。
对于第i天，很明显我们需要确保i-1天吃到西瓜，但是我们也可以选择这么一个策略：前面的西瓜还没有吃完，我买了新西瓜，把旧的西瓜扔了。
因此，我们选取一个p=min(f[j])i-1<=j<=n，显然对于这样取出来的p的j，对于第i天是合法的，而且这也是让前i-1天吃到西瓜的最有方案。
然后我们让f[i+b[i]-1]=min(p+a[i],f[i+b[i]-1]）
实际上，我们这么做是发现，如果f[i+1]<f[i]，我们可以用f[i+1]来替换f[i],但是如果一个个直接替换，太浪费时间。因此我们不选择替换，而是在决策时利用这个规律取值。
为了快速取得min(f[j])i-1<=j<=n,我们可以用一个线段树维护。
需要注意的一点是，它购买的总金额会很大，需要用long long 存，一开始用一个longlong级别的数来存f[i]的初值

#include <cstdio>

struct tree{
    int l,r,m;
    long long min;
};
int n;
int p[50001],d[50001];
long long o;
tree a[150001];

inline long long min(long long x,long long y)
{
    if(x<=y) return x; else return y;
}

inline void gengx(int k)
{
    a[k].min=min(a[k*2].min,a[k*2+1].min);
    return;
}

void make(int k,int l,int r)
{
    a[k].l=l;a[k].r=r;
    a[k].m=(l+r)/2;
    long long o=n;
    a[k].min=o*100000;
    if(l==r) return;
    make(k*2,l,a[k].m);
    make(k*2+1,a[k].m+1,r);
    gengx(k);
}

long long find(int k,int x)
{
    if(a[k].l>=x) return a[k].min;
    if(a[k].m<x) return find(k*2+1,x);
    else return min(find(k*2,x),find(k*2+1,x));
}

void insert(int k,long long s,int x)
{
    if(a[k].l==a[k].r) 
    {
        a[k].min=min(a[k].min,s);
        return;
    }
    if(x<=a[k].m) insert(k*2,s,x);
    else insert(k*2+1,s,x);
    gengx(k);
    return;
}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++) scanf("%d",&p[i]);
        for(int i=1;i<=n;i++) scanf("%d",&d[i]);
        make(1,1,n);
        for(int i=1;i<=n;i++)
        {
            if(i==1) o=0; else o=find(1,i-1);
            insert(1,o+p[i],i+d[i]-1);
        }
        printf("%lld\n",find(1,n));
    }
    return 0;
}
 by hzwlzrj

这道题的意思是告诉你每天的西瓜要多少钱，以及这个西瓜可以吃几天，然后问你怎么买，可以每天吃西瓜且花钱最少。

因为买了一个新的西瓜，之前的西瓜无论有没有吃完，都没用了，所以购买策略应该是从前往后进行。

我们用f[i]表示，前i天能够吃到西瓜，需要多少钱。记a[i],b[i]表示第i天的西瓜的价格和可以吃的天数，接下来我们来思考状态转移。

对于第i天，很明显我们需要确保i-1天吃到西瓜，但是我们也可以选择这么一个策略：前面的西瓜还没有吃完，我买了新西瓜，把旧的西瓜扔了。

因此，我们选取一个p=min(f[j])i-1<=j<=n，显然对于这样取出来的p的j，对于第i天是合法的，而且这也是让前i-1天吃到西瓜的最有方案。

然后我们让f[i+b[i]-1]=min(p+a[i],f[i+b[i]-1]）

实际上，我们这么做是发现，如果f[i+1]

为了快速取得min(f[j])i-1<=j<=n,我们可以用一个线段树维护。

需要注意的一点是，它购买的总金额会很大，需要用long long 存，一开始用一个longlong级别的数来存f[i]的初值

#include

struct tree{

int l,r,m;

long long min;

};

int n;

int p[50001],d[50001];

long long o;

tree a[150001];

inline long long min(long long x,long long y)

{

if(x<=y) return x; else return y;

}

inline void gengx(int k)

{

a[k].min=min(a[k*2].min,a[k*2+1].min);

return;

}

void make(int k,int l,int r)

{

a[k].l=l;a[k].r=r;

a[k].m=(l+r)/2;

long long o=n;

a[k].min=o*100000;

if(l==r) return;

make(k*2,l,a[k].m);

make(k*2+1,a[k].m+1,r);

gengx(k);

}

long long find(int k,int x)

{

if(a[k].l>=x) return a[k].min;

if(a[k].m

else return min(find(k*2,x),find(k*2+1,x));

}

void insert(int k,long long s,int x)

{

if(a[k].l==a[k].r)

{

a[k].min=min(a[k].min,s);

return;

}

if(x<=a[k].m) insert(k*2,s,x);

else insert(k*2+1,s,x);

gengx(k);

return;

}

int main()

{

while(scanf("%d",&n)!=EOF)

{

for(int i=1;i<=n;i++) scanf("%d",&p[i]);

for(int i=1;i<=n;i++) scanf("%d",&d[i]);

make(1,1,n);

for(int i=1;i<=n;i++)

{

if(i==1) o=0; else o=find(1,i-1);

insert(1,o+p[i],i+d[i]-1);

}

printf("%lld\n",find(1,n));

}

return 0;

}

by hzwlzrj