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

2024-06-15 12:18

本文主要是介绍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 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.

输出

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

样例输出

11

让我做 是对于每一天的西瓜可以吃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的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1063430

相关文章

Vue3 的 shallowRef 和 shallowReactive:优化性能

大家对 Vue3 的 ref 和 reactive 都很熟悉,那么对 shallowRef 和 shallowReactive 是否了解呢? 在编程和数据结构中,“shallow”(浅层)通常指对数据结构的最外层进行操作,而不递归地处理其内部或嵌套的数据。这种处理方式关注的是数据结构的第一层属性或元素,而忽略更深层次的嵌套内容。 1. 浅层与深层的对比 1.1 浅层(Shallow) 定义

HDFS—存储优化(纠删码)

纠删码原理 HDFS 默认情况下,一个文件有3个副本,这样提高了数据的可靠性,但也带来了2倍的冗余开销。 Hadoop3.x 引入了纠删码,采用计算的方式,可以节省约50%左右的存储空间。 此种方式节约了空间,但是会增加 cpu 的计算。 纠删码策略是给具体一个路径设置。所有往此路径下存储的文件,都会执行此策略。 默认只开启对 RS-6-3-1024k

使用opencv优化图片(画面变清晰)

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化,使其看起来更清晰,同时保持尺寸不变,通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多,主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器:相机传

hdu4826(三维DP)

这是一个百度之星的资格赛第四题 题目链接:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意:从左上角的点到右上角的点,每个点只能走一遍,走的方向有三个:向上,向下,向右,求最大值。 咋一看像搜索题,先暴搜,TLE,然后剪枝,还是TLE.然后我就改方法,用DP来做,这题和普通dp相比,多个个向上

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

hdu1394(线段树点更新的应用)

题意:求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质,在0到n-1这些数字组成的乱序排列,将第一个数字A移到最后一位,得到的逆序数为res-a+(n-a-1) 知道上面的知识点后,可以用暴力来解 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in

hdu1689(线段树成段更新)

两种操作:1、set区间[a,b]上数字为v;2、查询[ 1 , n ]上的sum 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdl

hdu4865(概率DP)

题意:已知前一天和今天的天气概率,某天的天气概率和叶子的潮湿程度的概率,n天叶子的湿度,求n天最有可能的天气情况。 思路:概率DP,dp[i][j]表示第i天天气为j的概率,状态转移如下:dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下: #include <stdio.h>#include

usaco 1.1 Broken Necklace(DP)

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于: 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b