Luogu 1156
Luogu 1156
这题还算是比较简单，看着便有些思路。感觉和背包问题比较像。
题目来源: Luogu
题解
由题目可得，我们想要到达的最终状态是高度为0，而这个过程中我们需要确保生命值大于0。也就是说，这道题目中存在的分支是吃掉垃圾(增加生命值)还是堆垃圾(增加高度)。而类比于背包问题，我们使用dp[i][j]=k来存储状态。其中i,j,k分别为高度，当前为第几个垃圾，生命值。
明显可以看出，在同一高度时生命值越高越好。所以，我们便可以大致得出以下的状态转移方程:
$ dp[i][j] = Max( dp[i][j] + f[j], dp[i-h[j]][j]) $
在这里，我们假设t[j],f[j],h[j]分别为垃圾的放入时间，所加生命值，高度。
注意，上述方程中分别代表吃垃圾和堆垃圾两种选择，而这两种选择必须是基于原本奶牛是存活的状态下才能执行，所以对于左右的两个式子，必须分别要求\(dp[i][j] \geq t[j]\)和\(dp[i-h[j]][j] \geq t[j]\)才能成立。
因为该方程与背包较为相似，所以我们也能发现该数组可以改为只包含高度的一位数组，最后在循环体内只要令高度的循环从高到低就好了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include <cstdio>
#include <algorithm>
#include <cstring>
int dp[110];
struct Garbage //存储有关垃圾的数据
{
trueint t,f,h;
trueconst bool operator <(const Garbage& tmp)const{
truetruereturn t<tmp.t;
true}
}garbage[110];
int main()
{
truememset(dp, 0, sizeof(0));
trueint d,g;
truescanf("%d%d", &d, &g);
truefor (int i=1; i<=g; i++)
truetruescanf("%d%d%d", &garbage[i].t, &garbage[i].f, &garbage[i].h);
truestd::sort(garbage,garbage+1+g);
truedp[0] = 10;
truefor (int i = 1; i<=g; i++)
true{
truetruefor (int j = d; j>=0; j--)
truetrue{
truetruetrueif ( dp[j] >= garbage[i].t )
truetruetruetruedp[j] += garbage[i].f;
truetruetrueif ( j - garbage[i].h >= 0 && dp[ j - garbage[i].h ] >= garbage[i].t )
truetruetruetruedp[j] = std::max(dp[j], dp[ j - garbage[i].h ]);
truetrue}
truetrue
truetrueif (dp[d]>0)
truetrue{
truetruetrueprintf("%d",garbage[i].t);
truetruetruereturn 0;
truetrue}
true}
true
trueint last = 10;
truefor (int i = 1; i<=g; i++)
truetrueif ( garbage[i].t <= last )
truetruetruelast += garbage[i].f;
trueprintf("%d",last);
truereturn 0;
}
|