暑假生活开始了，夏日炎炎，集训队想要每天都吃到西瓜。已知n天，每天商店提供一个西瓜，不同的西瓜可以供集训队吃不同的天数，也有不同的价格，问集训队想保证每天都能吃到西瓜的最小花费。
单个数100000，数组大小50000，因此需要用线段树优化。
对于每天的西瓜，不取则从最小值数组里取出当前最小值，取的话则是找出最小值+当天的西瓜价格，并且线段树更新后k天的最小费用。
dp[i][1]=min(dp[i-1][0],dp[i-1][1])+v[i];
dp[i][0]=query(i,i,1,n,1);
update(dp[i][1],i,min(n,i+d[i]-1),1,n,1);
由于最大值可能为50000*100000会超int，所以最大值inf要注意取大一点，比如1ll<<60
#include #include #include #include #include #include #include #include #define MAXN 100010#define INF (1ll<<60)#define ll long long#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;ll v[MAXN];ll d[MAXN];ll dp[MAXN][3];ll n;ll sum[MAXN<<2],add[MAXN<<2];void pushdown(ll rt){ if(add[rt]!=INF){ add[rt<<1] = min(add[rt<<1],add[rt]); add[rt<<1|1] = min(add[rt<<1|1],add[rt]); sum[rt<<1] = min(sum[rt<<1],add[rt]); sum[rt<<1|1] = min(sum[rt<<1|1],add[rt]); add[rt] = INF; }}void pushup(ll rt){ sum[rt] = min(sum[rt<<1],sum[rt<>1; build(lson); build(rson);}void update(ll c,ll L,ll R,ll l,ll r,ll rt){ if(L<=l if(Lm) update(c,L,R,rson); pushup(rt);}ll query(ll L,ll R,ll l,ll r,ll rt){ if(L<=l ll ans = INF; if(Lm) ans = min(ans,query(L,R,rson)); return ans;}int main(){while(scanf("%lld",for(ll i=1;i<=n;i++){scanf("%lld",}for(ll i=1;i<=n;i++){scanf("%lld",}dp[1][0]=INF;dp[1][1]=v[1];update(v[1],1,min(n,d[1]),1,n,1);for(ll i=2;i<=n;i++){dp[i][1]=min(dp[i-1][0],dp[i-1][1])+v[i];dp[i][0]=query(i,i,1,n,1);update(dp[i][1],i,min(n,i+d[i]-1),1,n,1);}printf("%lld\n",min(dp[n][1],dp[n][0]));}return 0;}
ZOJ-3632 Watermelon Full of Water 线段树+DP
【本文来源：美国服务器 https://www.68idc.cn 复制请保留原URL】