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

相关文章

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 配

Vue3中的动态组件详解

《Vue3中的动态组件详解》本文介绍了Vue3中的动态组件,通过`component:is=动态组件名或组件对象/component`来实现根据条件动态渲染不同的组件,此外,还提到了使用`markRa... 目录vue3动态组件动态组件的基本使用第一种写法第二种写法性能优化解决方法总结Vue3动态组件动态

Android 悬浮窗开发示例((动态权限请求 | 前台服务和通知 | 悬浮窗创建 )

《Android悬浮窗开发示例((动态权限请求|前台服务和通知|悬浮窗创建)》本文介绍了Android悬浮窗的实现效果,包括动态权限请求、前台服务和通知的使用,悬浮窗权限需要动态申请并引导... 目录一、悬浮窗 动态权限请求1、动态请求权限2、悬浮窗权限说明3、检查动态权限4、申请动态权限5、权限设置完毕后

Java使用POI-TL和JFreeChart动态生成Word报告

《Java使用POI-TL和JFreeChart动态生成Word报告》本文介绍了使用POI-TL和JFreeChart生成包含动态数据和图表的Word报告的方法,并分享了实际开发中的踩坑经验,通过代码... 目录前言一、需求背景二、方案分析三、 POI-TL + JFreeChart 实现3.1 Maven

Java导出Excel动态表头的示例详解

《Java导出Excel动态表头的示例详解》这篇文章主要为大家详细介绍了Java导出Excel动态表头的相关知识,文中的示例代码简洁易懂,具有一定的借鉴价值,有需要的小伙伴可以了解下... 目录前言一、效果展示二、代码实现1.固定头实体类2.动态头实现3.导出动态头前言本文只记录大致思路以及做法,代码不进

vue基于ElementUI动态设置表格高度的3种方法

《vue基于ElementUI动态设置表格高度的3种方法》ElementUI+vue动态设置表格高度的几种方法,抛砖引玉,还有其它方法动态设置表格高度,大家可以开动脑筋... 方法一、css + js的形式这个方法需要在表格外层设置一个div,原理是将表格的高度设置成外层div的高度,所以外层的div需要