精华内容
下载资源
问答
  • Watermelon Full of Water

    2017-08-24 03:06:06
    Watermelon is very popular in the hot summer. Students in ZJU-ICPC Team also love watermelon very much and they hope that they can have watermelon to eat every day during the summer vacation....
  •   题目大意: 暑假有n(1~50000)天,第i天西瓜的价格是p[i],可以吃d[i]天,如果在第i天买了个西瓜,那么旧的西瓜要扔掉,开始吃新西瓜。 问每天都能吃到西瓜的最小花费。...p[i]表示第i天买喜欢的花费,d[i]表...

    题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4778

     

    题目大意:

    暑假有n(1~50000)天,第i天西瓜的价格是p[i],可以吃d[i]天,如果在第i天买了个西瓜,那么旧的西瓜要扔掉,开始吃新西瓜。

    问每天都能吃到西瓜的最小花费。

     

     

    题目思路:

    p[i]表示第i天买喜欢的花费,d[i]表示第i天买的西瓜能吃的天数。

    dp[i],表示以i为起点,最少要花费多少钱才能使i~n每天都有西瓜吃。

    状态转移很显然dp[i]= (i+d[i]>n)? p[i] : min{dp[i+1]~dp[i+d[i]]}+p[i]

    很明显在取dp[i+1]~dp[i+d[i]]的过程显然不可以从i+1 ~ i+d[i]扫一遍,这样复杂度O(n*n),会超时。

    所以最直接的方法就是用线段树优化

     

    代码:

    #include <stdlib.h>
    #include <string.h>
    #include <stdio.h>
    #include <ctype.h>
    #include <math.h>
    #include <stack>
    #include <queue>
    #include <map>
    #include <set>
    #include <vector>
    #include <string>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    #define ll long long
    #define ls rt<<1
    #define rs ls|1
    #define lson l,mid,ls
    #define rson mid+1,r,rs
    #define middle (l+r)>>1
    #define clr_all(x,c) memset(x,c,sizeof(x))
    #define clr(x,c,n) memset(x,c,sizeof(x[0])*(n+1))
    #define eps (1e-8)
    #define MOD 1000000007
    #define INF 0x3f3f3f3f
    #define PI (acos(-1.0))
    #pragma comment(linker, "/STACK:102400000,102400000")
    template <class T> T _max(T x,T y){return x>y? x:y;}
    template <class T> T _min(T x,T y){return x<y? x:y;}
    template <class T> T _abs(T x){return (x < 0)? -x:x;}
    template <class T> T _mod(T x,T y){return (x > 0)? x%y:((x%y)+y)%y;}
    template <class T> void _swap(T &x,T &y){T t=x;x=y;y=t;}
    template <class T> void getmax(T& x,T y){x=(y > x)? y:x;}
    template <class T> void getmin(T& x,T y){x=(x<0 || y<x)? y:x;}
    int TS,cas=1;
    const int M=50000+5;
    ll n,p[M],d[M],mmin[M<<2],MAX;
    void build(int l,int r,int rt){
    	mmin[rt]=MAX;
    	if(l==r) return;
    	int mid=middle;
    	build(lson),build(rson);
    }
    void pushUp(int rt){
    	mmin[rt]=_min(mmin[ls],mmin[rs]);
    }
    void update(int l,int r,int rt,int p,ll c){
    	if(l==r){mmin[rt]=c;return;}
    	int mid=middle;
    	if(p<=mid) update(lson,p,c);
    	else update(rson,p,c);
    	pushUp(rt);
    }
    ll query(int l,int r,int rt,int L,int R){
    	if(L<=l && r<=R) return mmin[rt];
    	int mid=middle;
    	if(R<=mid) return query(lson,L,R);
    	else if(mid<L) return query(rson,L,R);
    	else return _min(query(lson,L,mid),query(rson,mid+1,R));
    }
    
    void run(){
    	int i,j;
    	MAX=1;
    	for(i=1;i<=n;i++) scanf("%lld",&p[i]),MAX+=p[i];
    	for(i=1;i<=n;i++) scanf("%lld",&d[i]);
    	ll ret,tmp;
    	build(1,n,1);
    	for(i=n;i>=1;i--){
    		int l=i+1,r=i+d[i];
    		if(r>n) ret=p[i];
    		else ret=query(1,n,1,i+1,i+d[i])+p[i];
    		update(1,n,1,i,ret);
    	}
    	printf("%lld\n",ret);
    }
    
    void preSof(){
    }
    
    int main(){
        //freopen("input.txt","r",stdin);
        //freopen("output.txt","w",stdout);
        preSof();
        //run();
        while((~scanf("%d",&n))) run();
        //for(scanf("%d",&TS);cas<=TS;cas++) run();
        return 0;
    }
    


     

     

    展开全文
  • ZOJ Problem Set - 3632 ...Watermelon Full of WaterTime Limit: 3 Seconds Memory Limit: 65536 KB Watermelon is very popular in the hot summer. Students in ZJU-ICPC Team also love watermelon very...
    ZOJ Problem Set - 3632
    Watermelon Full of Water

    Time Limit: 3 Seconds      Memory Limit: 65536 KB

    Watermelon is very popular in the hot summer. Students in ZJU-ICPC Team also love watermelon very much and they hope that they can have watermelon to eat every day during the summer vacation. Suppose there are n days and every day they can buy only one watermelon. The price of watermelon may be different in each day. Besides, sometimes the watermelon they choose to buy may be very big, which means if they buy this watermelon, they will need several days to eat it up. The students want to spend the minimum money to buy enough watermelon so that they can eat watermelon every day. Can you help them?

    Notice: When they buy a new watermelon, if they still have an old watermelon, they will throw the old one into dustbin. For example, suppose they buy a watermelon on the fisrt day, and it needs 4 days to eat up the watermelon. But if they buy a new watermelon on the second day and it needs 2 days to eat up the new watermelon, then they will throw the old one, and they have to buy a new watermelon on the fourth day since they don't have any watermelon to eat on that day.

    Input

    The input contains multiple test cases ( no more than 200 test cases ).
    In each test case, first there is an integer, n ( 1 <= n <=50000 ) , which is the number of summer days.
    Then there is a line containing n positive integers with the ith integer indicating the price of the watermelon on the ith day.
    Finally there is line containing n positive integers with the ith integer indicating the number of days students need to eat up the watermelon bought on the ith day.
    All these integers are no more than 100000 and integers are seperated by a space.

    Output

    For each case, output one line with an integer which is the minimum money they must spend so that they can have watermelon to eat every day.

    Sample Input

    4
    10 20 1 40
    3 2 3 1
    

    Sample Output

    11
    

    Author: HUANG, Qiao
    Contest: ZOJ Monthly, July 2012
    //动规加线段树优化

    #include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #define N 50005 #define Max 1000000000000000 #define lson l,m,k<<1 #define rson m+1,r,k<<1|1 using namespace std; long long Min[N<<2]; int p[N],last[N]; long long dp[N]; void build(int l,int r,int k) { Min[k]=Max; if(l==r) return; int m=(l+r)>>1; build(lson); build(rson); } void up(int &k) { Min[k]=min(Min[k<<1],Min[k<<1|1]); } long long val; void update(int &index,int l,int r,int k) { if(l==r)//更新每天买的西瓜最远可以持续到的天数 { Min[k]=min(val,Min[k]); return ; } int m=(l+r)>>1; if(index<=m) update(index,lson); else update(index,rson); up(k); } long long query(int &L,int &R,int l,int r,int k) { if(L<=l&&R>=r) { return Min[k]; } int m=(l+r)>>1; long long t1=Max,t2=Max; if(L<=m) t1=query(L,R,lson); if(R>m) t2=query(L,R,rson); return min(t1,t2); } int main() { int n; int i,k; while(scanf("%d",&n)!=EOF) { for(i=1;i<=n;i++) scanf("%d",&p[i]); for(i=1;i<=n;i++) scanf("%d",&last[i]); build(1,n,1); dp[0]=0; for(i=1;i<=n;i++) { k=last[i]+i-1; k=k>n?n:k;val=dp[i-1]+p[i]; update(k,1,n,1); dp[i]=query(i,n,1,n,1);//从当前到结束找到最小的 } printf("%lld\n",dp[n]); } return 0; }
    //还有一种是用优先队列优化,经测试,线段树优化要快点
    #include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <algorithm>
    #include <queue>
    #define N 50005
    using namespace std;
    long long Min[N<<2];
    int p[N],last[N];
    long long dp[N];
    struct node
    {
        long val;
        int last;
        bool operator<(const node& a)const
        {
            return val>a.val;
        }
    };
    int main()
    {
        int n;
        int i;
        while(scanf("%d",&n)!=EOF)
        {
            for(i=1;i<=n;i++)
             scanf("%d",&p[i]);
            for(i=1;i<=n;i++)
             scanf("%d",&last[i]);
           priority_queue<node> q;
              node temp;
            dp[1]=p[1];
            temp.val=p[1]; temp.last=last[1];
            q.push(temp);
           for(i=2;i<=n;i++)
           {
               temp.val=dp[i-1]+p[i];
               temp.last=last[i]+i-1;
               q.push(temp);
               while(q.top().last<i) q.pop();
               dp[i]=q.top().val;
           }
           printf("%lld\n",dp[n]);
        }
        return 0;
    }


    转载于:https://www.cnblogs.com/372465774y/archive/2012/08/05/2623656.html

    展开全文
  • 1518. Water Bottles

    2020-10-20 23:13:45
    Given numBottles full water bottles, you can exchange numExchange empty water bottles for one full water bottle. The operation of drinking a full water bottle turns it into an empty bottle. Return ...
    1. Water Bottles
      Given numBottles full water bottles, you can exchange numExchange empty water bottles for one full water bottle.

    The operation of drinking a full water bottle turns it into an empty bottle.

    Return the maximum number of water bottles you can drink.

    Example 1:

    在这里插入图片描述

    Input: numBottles = 9, numExchange = 3
    Output: 13
    Explanation: You can exchange 3 empty bottles to get 1 full water bottle.
    Number of water bottles you can drink: 9 + 3 + 1 = 13.
    Example 2:

    在这里插入图片描述

    Input: numBottles = 15, numExchange = 4
    Output: 19
    Explanation: You can exchange 4 empty bottles to get 1 full water bottle.
    Number of water bottles you can drink: 15 + 3 + 1 = 19.
    Example 3:

    Input: numBottles = 5, numExchange = 5
    Output: 6
    Example 4:

    Input: numBottles = 2, numExchange = 3
    Output: 2

    class Solution {
    public:
        int numWaterBottles(int numBottles, int numExchange) {
            int res=numBottles, empty=numBottles;
            while(empty>=numExchange)
            {
                res+=empty/numExchange;
                empty=empty/numExchange+empty%numExchange;
            }
            return res;
        }
    };
    
    展开全文
  • Watermelon Full of Water Time Limit: 3 Seconds Memory Limit: 65536 KB Watermelon is very popular in the hot summer. Students in ZJU-ICPC Team also love watermelon very much and they hope

    Watermelon Full of Water

    Time Limit: 3 Seconds      Memory Limit: 65536 KB

    Watermelon is very popular in the hot summer. Students in ZJU-ICPC Team also love watermelon very much and they hope that they can have watermelon to eat every day during the summer vacation. Suppose there are n days and every day they can buy only one watermelon. The price of watermelon may be different in each day. Besides, sometimes the watermelon they choose to buy may be very big, which means if they buy this watermelon, they will need several days to eat it up. The students want to spend the minimum money to buy enough watermelon so that they can eat watermelon every day. Can you help them?

    Notice: When they buy a new watermelon, if they still have an old watermelon, they will throw the old one into dustbin. For example, suppose they buy a watermelon on the fisrt day, and it needs 4 days to eat up the watermelon. But if they buy a new watermelon on the second day and it needs 2 days to eat up the new watermelon, then they will throw the old one, and they have to buy a new watermelon on the fourth day since they don't have any watermelon to eat on that day.

    Input

    The input contains multiple test cases ( no more than 200 test cases ).
    In each test case, first there is an integer, n ( 1 <= n <=50000 ) , which is the number of summer days.
    Then there is a line containing n positive integers with the ith integer indicating the price of the watermelon on the ith day.
    Finally there is line containing n positive integers with the ith integer indicating the number of days students need to eat up the watermelon bought on the ith day.
    All these integers are no more than 100000 and integers are seperated by a space.

    Output

    For each case, output one line with an integer which is the minimum money they must spend so that they can have watermelon to eat every day.

    Sample Input

    4
    10 20 1 40
    3 2 3 1
    

    Sample Output

    11

    题意:每天可以买一个西瓜,每个西瓜有相应的价钱,和可以吃多少天,要求每天都吃西瓜,问你最少的花费是多少。

    思路:首先逆推,第k天的最小花费是num1[k]+dp[k+  (1...num2[k])  ],然后因为数据量比较大,需要用线段树来得到后面部分的最小值是多少。

    AC代码如下:

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    long long dp[50010],num1[50010],num2[50010];
    int t=0,f[50010];
    struct node
    { long long l,r,minn;
      int pos;
    }tree[200010];
    void build(int num,int x,int y)
    { tree[num].l=x;
      tree[num].r=y;
      if(x==y)
      { tree[num].minn=100000*100000;
        tree[num].pos=++t;
        f[x]=num;
        return;
      }
      int mid=(tree[num].l+tree[num].r)/2;
      int left=2*num;
      int right=left+1;
      build(left,x,mid);
      build(right,mid+1,y);
      if(tree[left].minn<tree[right].minn)
      { tree[num].minn=tree[left].minn;
        tree[num].pos=tree[left].pos;
      }
      else
      { tree[num].minn=tree[right].minn;
        tree[num].pos=tree[right].pos;
      }
    }
    void update(int num,int x)
    { tree[num].minn=x;
      num/=2;
      int left,right;
      while(num>0)
      { left=2*num;right=left+1;
        if(tree[left].minn<tree[right].minn)
        { tree[num].minn=tree[left].minn;
          tree[num].pos=tree[left].pos;
        }
        else
        { tree[num].minn=tree[right].minn;
          tree[num].pos=tree[right].pos;
        }
        num/=2;
      }
    }
    int query(int num,int x,int y)
    { if(tree[num].l==x && tree[num].r==y)
       return tree[num].pos;
      int mid=(tree[num].l+tree[num].r)/2;
      int left=2*num;
      int right=left+1;
      if(y<=mid)
       return query(left,x,y);
      else if(x>mid)
       return query(right,x,y);
      else
      { int pos1,pos2;
        pos1=query(left,x,mid);
        pos2=query(right,mid+1,y);
        if(dp[pos1]<dp[pos2])
         return pos1;
        else
         return pos2;
      }
    }
    int main()
    { int n,i,j,k;
      while(~scanf("%d",&n))
      { t=0;
        for(i=1;i<=n;i++)
         scanf("%d",&num1[i]);
        for(i=1;i<=n;i++)
         scanf("%d",&num2[i]);
        dp[n]=num1[n];
        build(1,1,n+1);
        for(i=n-1;i>=1;i--)
        { if(i+num2[i]>=n+1)
           dp[i]=num1[i];
          else
           dp[i]=min(dp[i+1]+num1[i],dp[query(1,i+1,i+num2[i])]+num1[i]);
          update(f[i],dp[i]);
        }
        printf("%lld\n",dp[1]);
      }
    }
    




    展开全文
  • <p>The world is full of water, I tried editing server.properties and changing the seed and creating new worlds, but same results. <h3>Steps to Reproduce <h3>Debug information <ul><li>Debug link:...
  • K - Watermelon Full of Water Time Limit:3000MS Memory Limit:65536KB 64bit IO Format:%lld & %llu Submit Status Practice ZOJ 3632 Appoint description: Description Watermelon is very p...
  • 题目地址:  http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4778   算是基础的线段树题目了。。。   囧的一逼。。... 先是 tmin数组越界,没报错,还把day数组的值给改了。...
  • leetcode 1518 Water Bottles

    2020-08-12 22:25:55
    GivennumBottlesfull water bottles, you can exchangenumExchangeempty water bottles for one full water bottle. The operation of drinking a full water bottle turns it into an empty bottle. Return ...
  • <div><p>Due to the ability to add water to a full shallow well you're able to spam click a shallow well from full to one charge within 10 seconds depending on your luck. This means within seconds ...
  • Description n天,每天都要吃西瓜,第i天可以花p[i]的代价买一个可以吃第d[i]天的大西瓜,如果某天买了新的西瓜就会把没吃完的西瓜都扔掉吃新的西瓜,问n天都吃西瓜的最小代价 Input 多组用例,每组用例首先输入...
  • 题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3632 题目
  • ZOJ 3632 Watermelon Full of Water 线段树

    千次阅读 2013-08-14 10:47:42
    线段树 题意:给定n表示n天,第一行为n天每天西瓜价格,第二行为该天买的西瓜能吃的天数 问,每天都要有西瓜吃,到n天花的钱的最小值(注意,当买了第k天的西瓜,则之前的西瓜将被丢弃,也就是说,天数的计算取决于...
  • 优先队列优化下的DP,dp[i]记录的是吃到i天的最小花费,最后dp[N]即为答案。 View Code const int MM = 111111; #define debug puts("wrong") typedef long long int64;...
  • Watermelon Full of Water 时间限制(普通/Java):3000MS/9000MS 运行内存限制:65536KByte 描述 Watermelon is very popular in the hot summer. Students in ZJU-ICPC Team also love watermelon very much and...
  • <div><p>0.C-21983-g9432266174 <p>Get a sealed tin/aluminum can or a glass ...ll be able to use the full can/bottle to boil water.</p><p>该提问来源于开源项目:CleverRaven/Cataclysm-DDA</p></div>
  • Given numBottles full water bottles, you can exchange numExchange empty water bottles for one full water bottle. The operation of drinking a full water bottle turns it into an empty bottle. Return the...
  • Watermelon Full of Water Time Limit: 3 Seconds Memory Limit: 65536 KB Watermelon is very popular in the hot summer. Students in ZJU-ICPC Team also love watermelon very much and they hope
  • 描述:Given numBottles full water bottles, you can exchange numExchange empty water bottles for one full water bottle. The operation of drinking a full water bottle turns it into an empty bottle. ...
  • n天要保证每天都有西瓜吃,每天都可以买一个西瓜,每天的西瓜有不同的价格且可以吃不同的天数,求最小花费。 dp[i]=min(dp[k]+money[i]),day[k]+k>=i;用线段树维护dp[i]; #include #include ...
  • 暑假生活开始了,夏日炎炎,集训队想要每天都吃到西瓜。已知n天,每天商店提供一个西瓜,不同的西瓜可以供集训队吃不同的天数,也有不同的价格,问集训队想保证每天都能吃到西瓜的最小花费。 单个数100000,数组...
  • 题目大意: 让每天都能吃到西瓜。最少须要花多少钱。 思路分析: ...dp[pos] 就表示 要让 前i天每天都有西瓜吃。...然后再在每一个西瓜的更新部分取最小的,就能够是这个点所能得到的最小值。...事实上就是 dp[i] = min...
  • 题意:有个人每天都要吃西瓜。。。每天的西瓜的价钱不同,买了西瓜后,最多可以吃ti天,每天最多买一个西瓜,如果一天买了一个西瓜,那么之前买的就要丢掉。问n天花掉的最少多少钱能保证这个人每天都能吃到西瓜。...
  • 题意:  有n个点,每个点都有一个点权,每个点都有一条向右到达n点中一点的不等长线段。 总价值这样计算:  若取这条线段,就将该线段的最左端点的权值放入总花费中。 ... 能覆盖n个点的最小花费。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 709
精华内容 283
关键字:

fullwater