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

相关文章

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.

一文详解SpringBoot响应压缩功能的配置与优化

《一文详解SpringBoot响应压缩功能的配置与优化》SpringBoot的响应压缩功能基于智能协商机制,需同时满足很多条件,本文主要为大家详细介绍了SpringBoot响应压缩功能的配置与优化,需... 目录一、核心工作机制1.1 自动协商触发条件1.2 压缩处理流程二、配置方案详解2.1 基础YAML

MySQL中慢SQL优化的不同方式介绍

《MySQL中慢SQL优化的不同方式介绍》慢SQL的优化,主要从两个方面考虑,SQL语句本身的优化,以及数据库设计的优化,下面小编就来给大家介绍一下有哪些方式可以优化慢SQL吧... 目录避免不必要的列分页优化索引优化JOIN 的优化排序优化UNION 优化慢 SQL 的优化,主要从两个方面考虑,SQL 语

MySQL中慢SQL优化方法的完整指南

《MySQL中慢SQL优化方法的完整指南》当数据库响应时间超过500ms时,系统将面临三大灾难链式反应,所以本文将为大家介绍一下MySQL中慢SQL优化的常用方法,有需要的小伙伴可以了解下... 目录一、慢SQL的致命影响二、精准定位问题SQL1. 启用慢查询日志2. 诊断黄金三件套三、六大核心优化方案方案

Redis中高并发读写性能的深度解析与优化

《Redis中高并发读写性能的深度解析与优化》Redis作为一款高性能的内存数据库,广泛应用于缓存、消息队列、实时统计等场景,本文将深入探讨Redis的读写并发能力,感兴趣的小伙伴可以了解下... 目录引言一、Redis 并发能力概述1.1 Redis 的读写性能1.2 影响 Redis 并发能力的因素二、

使用国内镜像源优化pip install下载的方法步骤

《使用国内镜像源优化pipinstall下载的方法步骤》在Python开发中,pip是一个不可或缺的工具,用于安装和管理Python包,然而,由于默认的PyPI服务器位于国外,国内用户在安装依赖时可... 目录引言1. 为什么需要国内镜像源?2. 常用的国内镜像源3. 临时使用国内镜像源4. 永久配置国内镜

C#原型模式之如何通过克隆对象来优化创建过程

《C#原型模式之如何通过克隆对象来优化创建过程》原型模式是一种创建型设计模式,通过克隆现有对象来创建新对象,避免重复的创建成本和复杂的初始化过程,它适用于对象创建过程复杂、需要大量相似对象或避免重复初... 目录什么是原型模式?原型模式的工作原理C#中如何实现原型模式?1. 定义原型接口2. 实现原型接口3

Java嵌套for循环优化方案分享

《Java嵌套for循环优化方案分享》介绍了Java中嵌套for循环的优化方法,包括减少循环次数、合并循环、使用更高效的数据结构、并行处理、预处理和缓存、算法优化、尽量减少对象创建以及本地变量优化,通... 目录Java 嵌套 for 循环优化方案1. 减少循环次数2. 合并循环3. 使用更高效的数据结构4

Deepseek使用指南与提问优化策略方式

《Deepseek使用指南与提问优化策略方式》本文介绍了DeepSeek语义搜索引擎的核心功能、集成方法及优化提问策略,通过自然语言处理和机器学习提供精准搜索结果,适用于智能客服、知识库检索等领域... 目录序言1. DeepSeek 概述2. DeepSeek 的集成与使用2.1 DeepSeek API

Tomcat高效部署与性能优化方式

《Tomcat高效部署与性能优化方式》本文介绍了如何高效部署Tomcat并进行性能优化,以确保Web应用的稳定运行和高效响应,高效部署包括环境准备、安装Tomcat、配置Tomcat、部署应用和启动T... 目录Tomcat高效部署与性能优化一、引言二、Tomcat高效部署三、Tomcat性能优化总结Tom