学步园

现在，大学生可以在毕业之后去当兵啦.

今年，一共有n个大学生到你所在的部队来应征，你是一个综合兵营的总管，你的兵营共有海陆空三个兵种，由于每个大学生对不同的兵种有不同的能力值，现在请你安排这几个大学生到相应的兵种中去，使得他们的总战斗力最大，其中海军最多可以安排X人，陆军最多可以安排Y人，空军最多可以安排Z人.

当然，由于种种原因，有些兵种可能得不到足够的人，有些大学生也可能没有任何一个兵种愿意招收。

输入

先输入一个T(T<=110)，表示有T组数据，接下来每组数据的开始是一个数n(1<=n<=50)，表示有n个大学生，接下来的n行，每行3个整数a,b,c，a表示该大学生做海军的能力值，b表示该大学生做陆军的能力值,c表示该大学生做空军的能力值,(-100<=a,b,c<=100)。最后一行是3个整数X,Y,Z,(0<=X,Y,Z<=80)表示如题意。

输出

每个数据输出一行，有一个整数sum,表示合理安排这些大学生之后能够得到的最大的能力值。

样例输入

2
3
1 2 3
2 3 4
3 4 5
1 1 1
4
-1 2 5
3 6 2
4 7 5
10 7 2
2 0 1

样例输出

9
19

模拟题

#include <stdio.h>
#include <string.h>

int main()
{
	int test;
	int N, a[52], b[52], c[52];
	int X, Y, Z;
	int f[52][52][52], max;
	int sum, m, num, i, j, k;

	scanf("%d", &test);
	while(test--)
	{
		scanf("%d", &N);
		for (i = 1; i <= N; ++i)
			scanf("%d%d%d", &a[i], &b[i], &c[i]);
		scanf("%d%d%d", &X, &Y, &Z);
		X = X < N ? X : N;
		Y = Y < N ? Y : N;
		Z = Z < N ? Z : N;
		sum = (X + Y + Z) < N ? (X + Y + Z) : N;

		memset(f, 0, sizeof(f));
		max = -1;
		for (num = 1; num <= N; ++num)
			for (m = sum < num ? sum : num; m > 0; --m)
				for (i = 0; i <= X; ++i)
					for (j = 0; j <= Y && i + j <= m; ++j)
					{
						k = m - i - j;
						if (k <= Z)
						{
							if (i > 0 && a[num] > 0 && (f[i][j][k] < f[i - 1][j][k] + a[num]))
								f[i][j][k] = f[i - 1][j][k] + a[num];
							if (j > 0 && b[num] > 0 && (f[i][j][k] < f[i][j - 1][k] + b[num]))
								f[i][j][k] = f[i][j - 1][k] + b[num];
							if (k > 0 && c[num] > 0 && (f[i][j][k] < f[i][j][k - 1] + c[num]))
								f[i][j][k] = f[i][j][k - 1] + c[num];
							if (f[i][j][k] > max)
								max = f[i][j][k];
						}
					}
		printf("%d\n", max);
	}
	return 0;
}