给你n个工件，然后有A,B,C三个工厂，然后它们加工第i个工件所需要的时间分别为a[i],b[i],c[i]，然后现在要你利用三间工厂加工所有的零件，要求是任何时间工厂都不能停工，而且一定要三间同时做完。
理论上是很难突破时间限制的，但是发现sum(a[i]),sum(b[i]),sum(c[i])<=120，那么就可以这么搞 dp[n][x][y][z]表示利用前n个工件可以到达三间工厂的时间分别为x,y,z的转态，每加一个工件则转移多三种状态，因为最多不会有超过120*120*120状态，然后要转移40*120*120*120,有TLE的可能，不过感觉还是挺直接的dp，所以最后会发现其实是可以过的。
|
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 |
#pragma warning(disable:4996)#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<cmath>#include<vector>#include<queue>#define ll long long#define maxn 220#define eps 1e-7using
namespace std;int
dp[130][130][130];bool
vis[130][130][130];int
a[45], b[45], c[45];int
n;struct
Node{ int
a, b, c; Node(int
ai, int
bi, int
ci) :a(ai), b(bi), c(ci){} Node(){}};int
main(){ while
(cin >> n) { for
(int i = 0; i < n; i++){ scanf("%d%d%d", a + i, b + i, c + i); } queue<Node> que[2]; que[0].push(Node(0, 0, 0)); int
cur = 0, nxt = 1; Node x; for
(int i = 0; i < n; i++){ memset(vis, 0, sizeof(vis)); while
(!que[cur].empty()){ x = que[cur].front(); que[cur].pop(); if
(!vis[x.a + a[i]][x.b][x.c]) que[nxt].push(Node(x.a + a[i], x.b, x.c)), vis[x.a + a[i]][x.b][x.c] = true; if
(!vis[x.a][x.b + b[i]][x.c]) que[nxt].push(Node(x.a, x.b + b[i], x.c)), vis[x.a][x.b + b[i]][x.c] = true; if
(!vis[x.a][x.b][x.c + c[i]]) que[nxt].push(Node(x.a, x.b, x.c + c[i])), vis[x.a][x.b][x.c + c[i]] = true; } swap(cur, nxt); } memset(vis, 0, sizeof(vis)); while
(!que[cur].empty()){ Node x = que[cur].front(); que[cur].pop(); vis[x.a][x.b][x.c] = 1; } int
i; for
(i = 1; i <= 120; i++){ if
(vis[i][i][i]){ printf("%d\n", i); break; } } if
(i > 120) puts("NO"); } return
0;} |
ZOJ3554 A Miser Boss(dp),布布扣,bubuko.com
原文：http://www.cnblogs.com/chanme/p/3636801.html