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 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 containingnpositive integers with the ithinteger indicating the price of the watermelon on the ithday.Finally there is line containingnpositive integers with the ithinteger indicating the number of days students need to eat up the watermelon bought on the ithday.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 Input410 20 1 403 2 3 1Sample Output11
题意：有n天，每天都可以买西瓜，每个西瓜的价格是ai，每个西瓜能吃bi天。问这n天每天都有西瓜吃的最小的代价是多少？如果你在第i天买了一个西瓜，那么之前买的西瓜就要全部扔掉，才能开始吃新的西瓜。
题解：dp[i]表示前i天每天都有西瓜吃的最小花费，，则dp[i] = min (dp[i] , dp[ j – k +1] + val[j]);
单调队列优化：队列优先级为花费小的在先，大的在后。如果队首能带到当前位置i，则dp[i]=que.val;否则出队。
线段树优化：假设当前i买了西瓜，则【i,i+day[i]-1】这个区间的花费可以是dp[i-1]+val[i],线段树维护区间最小值即可，dp[i]=i点的值，线段树查询单点值。
#include<cstring>#include<algorithm>#include<iostream>#include<cmath>#include<cstdio>#include<queue>#define ll long long#define N 50050#define INF 999999999using namespace std;int n;int val[N],day[N];ll dp[N];struct Que {ll val,day;bool operator < (const Que &b)const {if(val==b.val)return day>b.day;return val>b.val;}};priority_queue<Que>que;int main() {//freopen("test.in","r",stdin);//debug();while(cin>>n) {for(int i=1; i<=n; i++) {scanf("%d",&val[i]);}for(int i=1; i<=n; i++) {scanf("%d",&day[i]);}while(que.size())que.pop();Que it;for(int i=1; i<=n; i++) {it.val=dp[i-1]+val[i],it.day=day[i]+i-1;while(que.size()&&que.top().day<i)que.pop();que.push(it);dp[i]=que.top().val;}printf("%lld\n",dp[n]);}return 0;}
#include<cstring>#include<algorithm>#include<iostream>#include<cmath>#include<cstdio>#include<queue>#define lson l,mid,idx<<1#define rson mid+1,r,idx<<1|1#define lc idx<<1#define rc idx<<1|1#define ll long long#define N 50050#define INF 99999999999using namespace std;int n;int val[N],day[N];ll dp[N],tree[N<<2];void push_up(int idx) {tree[idx]=min(tree[lc],tree[rc]);}void build(int l,int r,int idx) {tree[idx]=INF;if(l==r) {return;}int mid=(l+r)>>1;build(lson);build(rson);}void push_down(int idx) {if(tree[idx]!=INF) {tree[lc]=min(tree[lc],tree[idx]);tree[rc]=min(tree[rc],tree[idx]);tree[idx]=INF;}}void update(int l,int r,int idx,int x,int y,ll k) {if(l>=x&&r<=y) {tree[idx]=min(k,tree[idx]);return;}push_down(idx);int mid=(l+r)>>1;if(x<=mid)update(lson,x,y,k);if(y>mid)update(rson,x,y,k);}ll query(int l,int r,int idx,int x) {if(l==r) {return tree[idx];}push_down(idx);int mid=(l+r)>>1;if(x<=mid)return query(lson,x);elsereturn query(rson,x);}int main() {//freopen("test.in","r",stdin);while(cin>>n) {for(int i=1; i<=n; i++) {scanf("%d",&val[i]);}for(int i=1; i<=n; i++) {scanf("%d",&day[i]);}build(1,n,1);dp[0]=0;for(int i=1; i<=n; i++) {int R=i+day[i]-1;if(R>n)R=n;ll k=dp[i-1]+(ll)val[i];update(1,n,1,i,R,k);dp[i]=query(1,n,1,i);}printf("%lld\n",dp[n]);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
流过泪的眼睛更明亮，滴过血的心灵更坚强！
