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

相关文章

VUE动态绑定class类的三种常用方式及适用场景详解

《VUE动态绑定class类的三种常用方式及适用场景详解》文章介绍了在实际开发中动态绑定class的三种常见情况及其解决方案,包括根据不同的返回值渲染不同的class样式、给模块添加基础样式以及根据设... 目录前言1.动态选择class样式(对象添加:情景一)2.动态添加一个class样式(字符串添加:情

SpringCloud配置动态更新原理解析

《SpringCloud配置动态更新原理解析》在微服务架构的浩瀚星海中,服务配置的动态更新如同魔法一般,能够让应用在不重启的情况下,实时响应配置的变更,SpringCloud作为微服务架构中的佼佼者,... 目录一、SpringBoot、Cloud配置的读取二、SpringCloud配置动态刷新三、更新@R

如何用Python绘制简易动态圣诞树

《如何用Python绘制简易动态圣诞树》这篇文章主要给大家介绍了关于如何用Python绘制简易动态圣诞树,文中讲解了如何通过编写代码来实现特定的效果,包括代码的编写技巧和效果的展示,需要的朋友可以参考... 目录代码:效果:总结 代码:import randomimport timefrom math

Java中JSON字符串反序列化(动态泛型)

《Java中JSON字符串反序列化(动态泛型)》文章讨论了在定时任务中使用反射调用目标对象时处理动态参数的问题,通过将方法参数存储为JSON字符串并进行反序列化,可以实现动态调用,然而,这种方式容易导... 需求:定时任务扫描,反射调用目标对象,但是,方法的传参不是固定的。方案一:将方法参数存成jsON字

.NET利用C#字节流动态操作Excel文件

《.NET利用C#字节流动态操作Excel文件》在.NET开发中,通过字节流动态操作Excel文件提供了一种高效且灵活的方式处理数据,本文将演示如何在.NET平台使用C#通过字节流创建,读取,编辑及保... 目录用C#创建并保存Excel工作簿为字节流用C#通过字节流直接读取Excel文件数据用C#通过字节

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

usaco 1.3 Barn Repair(贪心)

思路:用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序,选取最大的M-1个作为间隙,其余地方用木板盖住。 做法: 1.若,板(M) 的数目大于或等于 牛棚中有牛的数目(C),则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则,先对 牛牛们的门牌号排序,然后 用一个数组 blank[ ] 记录两门牌号之间的距离,然后 用数组 an

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同