当前位置:网站首页>【练习-9】Zombie’s Treasure Chest
【练习-9】Zombie’s Treasure Chest
2022-07-06 09:26:00 【火焰车】
题目大意:
一些勇敢的战士来到一个失落的村庄。他们非常幸运,发现了很多宝藏和一个大宝箱,但也发现了愤怒的僵尸。
战士们非常勇敢,他们决定打败僵尸,然后把所有的宝藏都带回来。一场旷日持久的残酷战斗从早到晚持续着,战士们发现僵尸是不死的,不可战胜的。
当然,宝藏不应该留在这里。不幸的是,由于宝箱容量的限制,战士们无法用宝箱携带所有的宝藏。事实上,珍宝只有两种:祖母绿和蓝宝石。所有的祖母绿在大小和价值上都是相等的,而且数量是无限的。蓝宝石也是。
身为拥有魔法神器的战士们的牧师:电脑,考虑到箱子的大小,每种宝石的价值和大小,你应该计算出我们战士们能带回的宝藏的最大价值。
AC代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
const ll mod = 1e9+7;
struct node{
ll s,v;
};
node mx,mn,a[2];
int main()
{
int t,V;
cin>>t;
for(int i=1;i<=t;i++)
{
cin>>V>>a[0].s>>a[0].v>>a[1].s>>a[1].v;
ll t1 = a[0].v*a[1].s;
ll t2 = a[1].v*a[0].s;
ll res = 0;
if(t1>=t2)
mx.s=a[0].s,mx.v=a[0].v,mn.s=a[1].s,mn.v=a[1].v;
else
mx.s=a[1].s,mx.v=a[1].v,mn.s=a[0].s,mn.v=a[0].v;
ll top = V/mn.s;
top = min(top,mx.s-1);
for(ll j=0;j<=top;j++)
{
ll tmp1=j*mn.v;
ll tmp2=(V-j*mn.s)/mx.s*mx.v;
res = max(res,tmp1+tmp2);
}
printf("Case #%d: %lld\n",i,res);
}
return 0;
}
这道题简化的是取低价值物品数量的范围。
首先,我们知道:
箱子的体积是V
每个物品1 的体积是 s1,价值是 v1。
每个物品2 的体积是 s2 ,价值是v2。
那么当有s2个物品1时,物品1的体积是s2 * s1,价值是 s2 * v1.
同理当有s1个物品2时,物品2的体积是s1 * s2,价值是 s1 * v2.
很显然这时 :物品1的体积 = 物品2的体积,而 物品1 的价值 不一定等于 物品2的价值。
我们假设相同体积下物品1的价值更高:
也就是说体积相同时,s2 * v1 > s1 * v2.
反过来说,当有s1个物品2时他的价值必然低于 s2个物品1,那么物品2的数量肯定是小于s1的。
也就是说,物品1尽可能的取,而物品2最多取s1-1个。
当然这不是最简化的,明显取最小公倍数lcm时物品2取得个数会更少(时间复杂度更低)。
边栏推荐
- Research Report on market supply and demand and strategy of China's Medical Automation Industry
- 学习记录:STM32F103 时钟系统概述工作原理
- Eslint--- error: newline required at end of file but not found (EOL last) solution
- China chart recorder market trend report, technology dynamic innovation and market forecast
- B - 代码派对(女生赛)
- 区间和------离散化
- Research Report of pharmaceutical solvent industry - market status analysis and development prospect prediction
- Research Report on medical anesthesia machine industry - market status analysis and development prospect prediction
- 0-1背包問題(一)
- 学习记录:如何进行PWM 输出
猜你喜欢
C语言数组的概念
LeetCode#19. Delete the penultimate node of the linked list
ucorelab3
Learning record: STM32F103 clock system overview working principle
Learning record: Tim - Basic timer
STM32学习记录:玩转按键控制蜂鸣器和LED
UCORE Lab 1 system software startup process
基于web的照片数码冲印网站
STM32 learning record: input capture application
学习记录:STM32F103 时钟系统概述工作原理
随机推荐
Cost accounting [23]
Learning record: use STM32 external input interrupt
Market trend report, technical innovation and market forecast of lip care products in China and Indonesia
Research Report on surgical fluid treatment industry - market status analysis and development prospect prediction
csapp shell lab
China's PCB connector market trend report, technological innovation and market forecast
HDU - 6024 Building Shops(女生赛)
China potato slicer market trend report, technical dynamic innovation and market forecast
STM32学习记录:玩转按键控制蜂鸣器和LED
Matlab comprehensive exercise: application in signal and system
信息安全-威胁检测-NAT日志接入威胁检测平台详细设计
China's salt water membrane market trend report, technological innovation and market forecast
Market trend report, technological innovation and market forecast of pneumonia drugs obtained by Chinese hospitals
China earth moving machinery market trend report, technical dynamic innovation and market forecast
ucorelab3
ucorelab3
0 - 1 problème de sac à dos (1)
ucore lab5
ucorelab4
STM32 how to use stlink download program: light LED running light (Library version)