ZOJ3554 A Miser Boss(dp)

给你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，所以最后会发现其实是可以过的。

#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-7
using 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
", i);
				break;
			}
		}
		if (i > 120) puts("NO");
	}
	return 0;
}