[luoguP1507] NASA的食物计划（DP）

传送门

 

二位费用背包

 

——代码

复制代码 1 #include <cstdio> 2 #include <iostream> 3 4 int n, maxv, maxw; 5 int f[410][410]; 6 7 inline int read() 8 { 9 int x = 0, f = 1; 10 char ch = getchar(); 11 for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1; 12 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0'; 13 return x * f; 14 } 15 16 inline int max(int x, int y) 17 { 18 return x > y ? x : y; 19 } 20 21 int main() 22 { 23 int i, j, k, v, w, val; 24 maxv = read(); 25 maxw = read(); 26 n = read(); 27 for(i = 1; i <= n; i++) 28 { 29 v = read(); 30 w = read(); 31 val = read(); 32 for(j = maxv; j >= v; j--) 33 for(k = maxw; k >= w; k--) 34 f[j][k] = max(f[j][k], f[j - v][k - w] + val); 35 } 36 printf("%dn", f[maxv][maxw]); 37 return 0; 38 }

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
#include <cstdio>
#include <iostream>

int n, maxv, maxw;
int f[410][410];

inline int read()
{

int x = 0, f = 1;

char ch = getchar();

for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;

for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';

return x * f;
}

inline int max(int x, int y)
{

return x > y ? x : y;
}

int main()
{

int i, j, k, v, w, val;

maxv = read();

maxw = read();

n = read();

for(i = 1; i <= n; i++)

{

v = read();

w = read();

val = read();

for(j = maxv; j >= v; j--)

for(k = maxw; k >= w; k--)

f[j][k] = max(f[j][k], f[j - v][k - w] + val);

}

printf("%dn", f[maxv][maxw]);

return 0;
}