博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
洛谷 P1417 烹调方案 (01背包拓展)
阅读量:5855 次
发布时间:2019-06-19

本文共 1053 字,大约阅读时间需要 3 分钟。

一看到这道题就是01背包

但是我注意到价值和当前的时间有关。

没有想太多,直接写,0分

然后发现输入方式不对……

改了之后只有25分

我知道wa是因为时间会影响价值,但不知道怎么做。

后来看了题解,发现我对01背包理解不够透彻

普通01背包做下来放入物品的顺序是1到n的
因为这个时候顺序没有关系,所以可以直接做
但是这道题后面放的物品价值小,所以价值有关系
所以就要提前排好序。
排序的依据就判断相邻两个物品先后放的价值,
然后化简可以推出一个式子。
这里其实是一个贪心。
然后就做01背包就好了

然后注意开long long 

#include
#include
#include
#define REP(i, a, b) for(int i = (a); i < (b); i++)#define _for(i, a, b) for(int i = (a); i <= (b); i++)using namespace std;typedef long long ll;const int MAXN = 112;const int MAXM = 112345;ll f[MAXM];struct node { ll a, b, c; bool operator < (const node& rhs) const { return c * rhs.b < rhs.c * b; }}s[MAXN];int t, n;int main(){ scanf("%d%d", &t, &n); REP(i, 0, n) scanf("%lld", &s[i].a); REP(i, 0, n) scanf("%lld", &s[i].b); REP(i, 0, n) scanf("%lld", &s[i].c); sort(s, s + n); ll ans = 0; REP(i, 0, n) for(int j = t; j >= s[i].c; j--) { f[j] = max(f[j], f[j-s[i].c] + s[i].a - j * s[i].b); ans = max(ans, f[j]); } printf("%lld\n", ans); return 0;}

 

转载于:https://www.cnblogs.com/sugewud/p/9819383.html

你可能感兴趣的文章
CentOS 升级现有PHP版本
查看>>
(一) pyhon 基础语法(数值 字符串 元组 列表 字典)
查看>>
HDOJ 1003:求一串数字中和最大的连续子串
查看>>
RedHat 5.6_x86_64 + ASM + RAW+ Oracle 10g RAC (二)
查看>>
win7不能全屏
查看>>
MySQL/InnoDB的并发插入Concurrent Insert
查看>>
转两好文防丢:Debian 版本升级/降级 & Linux 应用程序失去输入焦点问题的解决...
查看>>
HDU - Pseudoforest
查看>>
Nexus杂
查看>>
Android --- GreenDao的实现(ORM框架)
查看>>
Linux平台Java调用so库-JNI使用例子
查看>>
Spring Data JPA
查看>>
项目管理修炼之道之规划项目
查看>>
Web服务器压力测试工具http_load、webbench、ab、Siege使用教程
查看>>
RHEL6.3 源码安装Puppet
查看>>
Mac软件下载备忘
查看>>
java 泛型初探
查看>>
在Linux中执行.sh脚本,异常/bin/sh^M: bad interpreter: No such file or directory
查看>>
就是一个表格
查看>>
CakePHP 2.x CookBook 中文版 第三章 入门 之 CakePHP 的结构
查看>>