TOJ 4369 ZOJ 3632 Watermelon Full of Water / 线段树优化DP

本文主要是介绍TOJ 4369 ZOJ 3632 Watermelon Full of Water / 线段树优化DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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 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.

输入

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 i_th integer indicating the price of the watermelon on the i_th day.
Finally there is line containing n positive integers with the i_th integer indicating the number of days students need to eat up the watermelon bought on the i_th day.
All these integers are no more than 100000 and integers are seperated by a space.

输出

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.

样例输入

4
10 20 1 40
3 2 3 1

样例输出

让我做是对于每一天的西瓜可以吃k天的话去更新 dp[i]到dp[i+k-1]的最小值用线段树成段更新

可以大神的做法就是更新i+k-1这一天然后询问的时候询问 i到n天的最小值

#include <stdio.h>
#include <string.h>
const long long Max = 1000000000000000;
using namespace std;
const long long MAX = 50010;
struct node
{long long l;long long r;long long min;
}a[MAX*4];
long long dp[MAX];
long long b[MAX];
long long c[MAX];long long min(long long x,long long y)
{return x < y ? x : y;
}
void build(long long l,long long r,long long rt)
{a[rt].l = l;a[rt].r = r;a[rt].min = Max;if(l == r)return;long long m = (l + r) >> 1;build(l,m,rt<<1);build(m+1,r,rt<<1|1);
}
long long query(long long x,long long y,long long rt)
{if(x <= a[rt].l && y >= a[rt].r)return a[rt].min;long long m = (a[rt].l + a[rt].r) >> 1;long long ret = Max;if(x <= m)ret = min(ret,query(x,y,rt<<1));if(y > m)ret = min(ret,query(x,y,rt<<1|1));return ret;
}void update(long long x,long long rt,long long mi)
{if(a[rt].l == a[rt].r){a[rt].min = min(mi,a[rt].min);return;}long long m = (a[rt].l + a[rt].r) >> 1;if(x <= m)update(x,rt<<1,mi);elseupdate(x,rt<<1|1,mi);a[rt].min = min(a[rt<<1].min,a[rt<<1|1].min);
}int main()
{long long i,j,k,n;while(scanf("%lld",&n)!=EOF){for(i = 1; i <= n; i++)scanf("%lld",&b[i]);for(i = 1; i <= n; i++)scanf("%lld",&c[i]);build(1,n,1);for(i = 1;i <= n; i++){j = i + c[i] - 1;if(j > n)j = n;k = dp[i-1] + b[i];update(j,1,k);dp[i] = query(i,n,1);}printf("%lld\n",dp[n]);}return 0;
}

这篇关于TOJ 4369 ZOJ 3632 Watermelon Full of Water / 线段树优化DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！