题解 - [Luogu P1507] NASA 的食物计划

发表于 更新于 分类于 ， 本文字数： 425 阅读时长 ≈ 2 分钟

题目链接

原始题面

题目背景

NASA (美国航空航天局) 因为航天飞机的隔热瓦等其他安全技术问题一直大伤脑筋，因此在各方压力下终止了航天飞机的历史，但是此类事情会不会在以后发生，谁也无法保证

在遇到这类航天问题时，解决方法也许只能让航天员出仓维修，但是多次的维修会消耗航天员大量的能量，因此 NASA 便想设计一种食品方案，让体积和承重有限的条件下多装载一些高卡路里的食物.

题目描述

航天飞机的体积有限，当然如果载过重的物品，燃料会浪费很多钱

每件食品都有各自的体积、质量以及所含卡路里

在告诉你体积和质量的最大值的情况下，请输出能达到的食品方案所含卡路里的最大值，当然每个食品只能使用一次.

输入输出格式

输入格式

第一行 两个数 体积最大值 (\(<400\)) 和质量最大值 (\(<400\))

第二行 一个数 食品总数 \(N\)(\(<50\)).

第三行－第 \(3+N\) 行

每行三个数 体积 (\(<400\)) 质量 (\(<400\)) 所含卡路里 (\(<500\))

输出格式

一个数 所能达到的最大卡路里

输入输出样例

输入样例 #1

1
2
3
4
5
6
320 350
4
160 40 120
80 110 240
220 70 310
40 400 220

输出样例 #1

1
550

说明 / 提示

很简单的背包...

解题思路

二维 01 背包板子题

代码参考

Show code

Luogu_P1507view raw
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
#define _for(i, l, r) for (auto i = (l); i <= (r); ++i)
#define _rfor(i, r, l) for (auto i = (r); i >= (l); --i)
namespace FastIO {
char buf[1 << 21], buf2[1 << 21], a[20], *p1 = buf, *p2 = buf, hh = '\n';
int p, p3 = -1;
int getc() {
  return p1 == p2 &&
             (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ?
           EOF :
           *p1++;
}
void read() {}
void print() {}
template <typename T, typename... T2>
void read(T &x, T2 &...oth) {
  int f = 0;
  x = 0;
  char ch = getc();
  while (!isdigit(ch)) {
    if (ch == '-') f = 1;
    ch = getc();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - 48;
    ch = getc();
  }
  if (f) x = -x;
  read(oth...);
}
void flush() { fwrite(buf2, 1, p3 + 1, stdout), p3 = -1; }
template <typename T, typename... T2>
void print(T x, T2... oth) {
  if (p3 > 1 << 20) flush();
  if (x < 0) buf2[++p3] = 45, x = -x;
  do { a[++p] = x % 10 + 48; } while (x /= 10);
  do { buf2[++p3] = a[p]; } while (--p);
  buf2[++p3] = hh;
  print(oth...);
}
template <typename T>
void print_h(T x, char h) {
  if (p3 > 1 << 20) flush();
  if (x < 0) buf2[++p3] = 45, x = -x;
  do { a[++p] = x % 10 + 48; } while (x /= 10);
  do { buf2[++p3] = a[p]; } while (--p);
  buf2[++p3] = h;
}
void putchar(char a) { buf2[++p3] = a; }
}  // namespace FastIO
using FastIO::print;
using FastIO::print_h;
using FastIO::read;
const int M = 50 + 5;
const int N = 400 + 5;
int V, Mass, n;
int f[N][N];
struct Food {
  int v, m, cal;
} a[M];
int main() {
  read(V, Mass, n);
  _for(i, 1, n) read(a[i].v, a[i].m, a[i].cal);
  _for(i, 1, n)
    _rfor(j, V, 0) {
      if (j >= a[i].v)
        _rfor(k, Mass, 0) {
          if (k >= a[i].m)
            f[j][k] = std::max(f[j][k], f[j - a[i].v][k - a[i].m] + a[i].cal);
        }
    }
  print(f[V][Mass]);
ex:
  FastIO::flush();
  return 0;
}