BUYING FEED(贪心+树状动态规划)

2024-09-08 02:38

本文主要是介绍BUYING FEED(贪心+树状动态规划),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

BUYING FEED

时间限制: 3000 ms  |  内存限制: 65535 KB
难度:4
描述

Farmer John needs to travel to town to pick up K (1 <= K <= 100)pounds of feed. Driving D miles with K pounds of feed in his truck costs D*K cents.

The county feed lot has N (1 <= N<= 100) stores (conveniently numbered 1..N) that sell feed. Each store is located on a segment of the X axis whose length is E (1 <= E <= 350). Store i is at location X_i (0 < X_i < E) on the number line and can sell John as much as F_i (1 <= F_i <= 100) pounds of feed at a cost of C_i (1 <= C_i <= 1,000,000) cents per pound.
Amazingly, a given point on  the X axis might have more than one store.

Farmer John  starts  at location 0 on this number line and can drive only in the positive direction, ultimately arriving at location E, with at least K pounds of feed. He can stop at any of the feed stores along the way and buy any amount of feed up to the the store's limit.  What is the minimum amount Farmer John has to pay to buy and transport the K pounds of feed? Farmer John
knows there is a solution. Consider a sample where Farmer John  needs two pounds of feed from three stores (locations: 1, 3, and 4) on a number line whose range is 0..5:     
0   1   2  3   4   5    
---------------------------------         
     1      1    1                Available pounds of feed         
     1     2     2               Cents per pound

It is best for John to buy one pound of feed from both the second and third stores. He must pay two cents to buy each pound of feed for a total cost of 4. When John travels from 3 to 4 he is moving 1 unit of length and he has 1 pound of feed so he must pay1*1 = 1 cents.

When John travels from 4 to 5 heis moving one unit and he has 2 pounds of feed so he must pay 1*2 = 2 cents. The total cost is 4+1+2 = 7 cents.

输入
The first line of input contains a number c giving the number of cases that follow
There are multi test cases ending with EOF.
Each case starts with a line containing three space-separated integers: K, E, and N
Then N lines follow :every line contains three space-separated integers: Xi Fi Ci
输出
For each case,Output A single integer that is the minimum cost for FJ to buy and transport the feed
样例输入
1
2 5 3 
3 1 2
4 1 2
1 1 1
样例输出
7


题目连接:点击打开链接


题意:有T组测试数据,有个人要去买k重量的东西,但他如果每带k(1....K)重量的东西走L距离时的花费为K*L(不带东西走花费为0),现在要从0点走到E点,有N个点卖东西,问题是要从那个店开始买东西到达E点时的花费最小?

思路:

求出每个商店(每一点)每买一磅食物需要的价钱,价钱中包括从这点运到终点需要的运费。

DP,转移方程(条件不同)

DP[I][J]=MIN{DP[I-1][K]+K*K*(D[I]-D[I-1])+(J-K)*C[I]}      J-F[I]<=K<=J

根据题目数据给的范围,500(I的范围)*10000(J的范围)*500(K的范围)肯定要超时。 

于是用单调队列优化。

关于单调队列:队头的元素肯定是最小的(最大的)

取元素操作:从队头取出元素,直到该元素在要求的范围内(本题即为J-F[I]<=K<=J

插入元素操作:若队尾元素比插入的元素要大,则删除。直到比待插入的元素小为止,然后再插入元素。

另外通过本题明确了队列的用法,头指针指向第一个元素,尾指针指向最后一个元素的后一位。若头尾指针相等则队列为空。

代码:

#include<iostream>
#include<cstdio>
#include<string>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;struct good
{int valu;//该点的价值int newvalu;//新的价值int nowpiont;//所在的点int mass;//该点的物品量
}goods[150];
bool cmp(good a,good b)
{return a.newvalu<b.newvalu;
}
int main()
{int t;int x,allpoint ,n;cin>>t;while(t--){cin>>x>>allpoint>>n;for(int i=0;i<n;i++){cin>>goods[i].nowpiont>>goods[i].mass>>goods[i].valu;goods[i].newvalu=allpoint-goods[i].nowpiont+goods[i].valu;}sort(goods,goods+n,cmp);int sum=0,cnt=0;for(int i=0;i<n;i++){if(cnt<x)//如果当前的重量不大于总重量{if(cnt+goods[i].mass<=x)//当前重量累加小于总重量{sum+=goods[i].newvalu*goods[i].mass;//当前的价值乘当前的重量cnt+=goods[i].mass;//重量累加if(cnt==x)break;//如过累加后的重量正好等于总重量,break}else{sum+=(x-cnt)*goods[i].newvalu;//如果当前的重量大于总重量,break;                           //只取其中的一部分}}}cout<<sum<<endl;}}




这篇关于BUYING FEED(贪心+树状动态规划)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu

基于Canvas的Html5多时区动态时钟实战代码

《基于Canvas的Html5多时区动态时钟实战代码》:本文主要介绍了如何使用Canvas在HTML5上实现一个多时区动态时钟的web展示,通过Canvas的API,可以绘制出6个不同城市的时钟,并且这些时钟可以动态转动,每个时钟上都会标注出对应的24小时制时间,详细内容请阅读本文,希望能对你有所帮助...

Vue中动态权限到按钮的完整实现方案详解

《Vue中动态权限到按钮的完整实现方案详解》这篇文章主要为大家详细介绍了Vue如何在现有方案的基础上加入对路由的增、删、改、查权限控制,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、数据库设计扩展1.1 修改路由表(routes)1.2 修改角色与路由权限表(role_routes)二、后端接口设计

前端 CSS 动态设置样式::class、:style 等技巧(推荐)

《前端CSS动态设置样式::class、:style等技巧(推荐)》:本文主要介绍了Vue.js中动态绑定类名和内联样式的两种方法:对象语法和数组语法,通过对象语法,可以根据条件动态切换类名或样式;通过数组语法,可以同时绑定多个类名或样式,此外,还可以结合计算属性来生成复杂的类名或样式对象,详细内容请阅读本文,希望能对你有所帮助...

Nginx实现动态封禁IP的步骤指南

《Nginx实现动态封禁IP的步骤指南》在日常的生产环境中,网站可能会遭遇恶意请求、DDoS攻击或其他有害的访问行为,为了应对这些情况,动态封禁IP是一项十分重要的安全策略,本篇博客将介绍如何通过NG... 目录1、简述2、实现方式3、使用 fail2ban 动态封禁3.1 安装 fail2ban3.2 配