luogu_1156: 垃圾陷阱
2024-09-05 22:10:11
洛谷1156:垃圾陷阱
题目描述:
- 一头牛在一个井里,深度为\(D(1\leq D\leq100)\)
- 每过一段时间会往井里投掷一个物品,牛可以选择将其堆起来或者吃掉,吃掉可以增加生命值(生命值随时间慢慢减少),堆起来就离出口更近一些。同时知道牛的初试生命值为\(10\)。
- 询问如果牛可以爬出井,输出一个整数表示最早什么时候能够爬出;否则输出这头牛最长可以存活多长时间。
输入格式:
- 第一行输入两个整数\(D\)和\(G\)表示深度和投入井的物品的数量。
- 加下来\(G\)行,每行输入\(3\)个整数:\(T(0<T\leq100)\),表示物品被投入井中的时间;\(F(1\leq F\leq30)\),表示物品能增加的生命值;\(H(1\leq H\leq25)\),该物品能垫多少高度。
输出格式:
- 输出一个整数表示答案。
思路:
- 背包问题
- 把井的深度看成是背包的容积。
- 把堆的物品的高度看成是物品的体积,得到的生命值看成是物品的价值。
- 那么题目的要求就是考虑最快装满背包的时间或者如果装不满就输出价值\(+(items(i).t)\)
- 首先将投入物品按照时间作为关键字排序。
- 那么对于牛来说,一件物品有吃掉它或者堆起来两种选择。
- 设\(f(i,j)\)表示在第\(i\)个物品时,高度为\(j\)的生命值最大值。
- 初始状态下: \(f(0,0)=10\),其他情况为\(-INF\)(其实这里我有点没搞懂,但是赋0就会wa掉,希望有人能评论区告诉我一下)
- \(f(i,j)=max(f(i,j), f(i-1,j)+items(i).v-(items(i).t)-items(i-1).t))\)
- \(f(i,j)=max(f(i,j),f(i-1,j-items(i).h)-(items(i).t-items(i-1).t))\)
- 那如果可以爬出来,这时候选一个时间最小值。
- 那如果不能爬出来,那么枚举一下\(f(i,j)\)的情况。
代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 110;
const int INF = 0x3f3f3f3f;
int D, G, f[maxn][100+10], ans;
struct Node{
int t, v, h;
}a[maxn];
bool cmp(Node a, Node b){
return a.t < b.t;
}
int main()
{
scanf("%d%d", &D, &G);
for(int i = 1; i <= G; i++){
auto &x = a[i];
scanf("%d%d%d", &x.t, &x.v, &x.h);
}
sort(a + 1, a + 1 + G, cmp);
for(int i = 0; i <= G; i++)
for(int j = 0; j <= D; j++) f[i][j] = -INF;
f[0][0] = 10;
for(int i = 1; i <= G; i++)
for(int j = 0; j <= D; j++)
{
if(f[i-1][j] >= a[i].t - a[i-1].t)
f[i][j] = max(f[i][j], f[i-1][j]+a[i].v-(a[i].t-a[i-1].t));
if(f[i-1][j-a[i].h] >= a[i].t-a[i-1].t && j >= a[i].h)
{
f[i][j] = max(f[i][j], f[i-1][j-a[i].h]-(a[i].t-a[i-1].t));
if(j == D)
{
printf("%d\n", a[i].t);
return 0;
}
}
}
ans = -1;
for(int i = 1; i <= G; i++)
for(int j = 0; j <= D; j++)
ans = max(ans, f[i][j] + a[i].t);
cout << ans << endl;
return 0;
}
最新文章
- 通过代理连接go01ge
- PLSQL_数据泵定参数批量导入多表Expdp/Impdp Parfile(案例)
- 重新起步 iOS 开发
- Server Tomcat v7.0 Server at localhost failed to start.错误可能原因之一
- ruby 疑难点之—— yield 和 yield self
- Java知识思维导图
- 24种设计模式--工厂方法模式【Factory Method Pattern】
- 那些我希望在一开始使用 Zsh(oh-my-zsh) 时就知道的
- HDU 5787 K-wolf Number(数位DP)
- Python关键字yield的解释
- zen coding一个牛的不行的html和css开发工具
- Find all factorial numbers less than or equal to N
- [bzoj3673] 可持久化并查集 by zky
- MySQL&#160;zip解压版安装过程及问题
- [偏序关系与CDQ分治]【学习笔记】
- Adaboost的意义
- Play Framework, Server Sent Events and Internet Explorer
- Java(五、类和对象中的例题)
- Shell语言
- Django集成OpenLDAP认证