hpc.cpp

datastructure, algorithms in C++ problem soloution

// 高性能计算机 参考程序
// written by starfish ([e-mail])
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>

#define FALSE 0
#define TRUE  1

#define INPUT_FILE  "hpc.in"
#define OUTPUT_FILE "hpc.out"
#define MAX_N 60
#define MAX_P 20
#define INFINITY INT_MAX/2		// 定义无穷大

//#define DEBUG_1
//#define DEBUG_2
//#define DEBUG_3
//#define DEBUG_4

FILE *fin, *fout;

int nA, nB, p;
int tA[MAX_P], tB[MAX_P], kA[MAX_P], kB[MAX_P];
int f[MAX_P][MAX_N+1][MAX_N+1];

int min(int a, int b) {
	return (a < b? a: b);
}

int max(int a, int b) {
	return (a > b? a: b);
}

int ReadCase()	// 读入数据
{
	int i;
	if (feof(fin))
		return FALSE;
	fscanf(fin, "%d%d", &nA, &nB);
	fscanf(fin, "%d", &p);
	for (i = 0; i < p; i++)
		fscanf(fin, "%d%d%d%d", &tA[i], &tB[i], &kA[i], &kB[i]);
	return (TRUE);
}

void Calf()
{
	int P[MAX_N+1][MAX_N+1][2];
	int i, a, b, w;
	
	for (i = 0; i < p; i++) 
	{	
		for (a = 0; a <= nA; a++)
			for (b = 0; b <= nB; b++)
			{
				if ((a == 0) && (b == 0)) {
					P[a][b][0] = 0;
					P[a][b][1] = 0;
				}
				else if (a==0) {
					P[a][b][0] = INFINITY;
					P[a][b][1] = tB[i]+kB[i]*b*b; 
				}
				else if (b==0) {
					P[a][b][0] = tA[i]+kA[i]*a*a;
					P[a][b][1] = INFINITY;
				}
				else {
					// 利用公式（1）
					P[a][b][1] = INFINITY;					
					for (w = 1; w <= b; w++)
						P[a][b][1] = min(P[a][b][1], P[a][b-w][0]+tB[i]+kB[i]*w*w);
					// 利用公式（2）
					P[a][b][0] = INFINITY;
					for (w = 1; w <= a; w++)
						P[a][b][0] = min(P[a][b][0], P[a-w][b][1]+tA[i]+kA[i]*w*w);								
				}
				f[i][a][b] = min(P[a][b][0], P[a][b][1]);
				#ifdef DEBUG_1
					printf("f[%d][%d][%d] = %d \n", i, a, b, f[i][a][b]);
				#endif
			}
	}
}



void SolveCase()
{
	int F[MAX_P][MAX_N+1][MAX_N+1];
	int i, a, b, ka, kb;

	Calf();			// 计算函数f

	// 计算函数F
	for (a = 0; a <= nA; a++)
		for (b = 0; b <= nB; b++) {
			F[0][a][b] = f[0][a][b];
			#ifdef DEBUG_3
				printf("F[%d][%d][%d] = %d \n", 0, a, b, F[0][a][b]);
			#endif
		}
	
	for (i = 1; i < p; i++)	
		for (a = 0; a <= nA; a++)
			for (b = 0; b <= nB; b++)
			{
				if ((a ==0) && (b == 0))
					F[i][a][b] = 0;
				else {
					F[i][a][b] = INFINITY;
					for (ka = 0; ka <= a; ka++)
						for (kb = 0; kb <= b; kb++)	{
							// 利用公式（8）
							F[i][a][b] = min(F[i][a][b], max(F[i-1][ka][kb], f[i][a-ka][b-kb]));
						#ifdef DEBUG_4							
							printf("f[%d][%d][%d] = %d \n", i, a-ka, b-kb, f[i][a-ka][b-kb]);
						#endif
						#ifdef DEBUG_3
							printf("ka = %d, kb = %d \n", ka, kb);
							printf("F[%d][%d][%d] = %d \n", i, a, b, F[i][a][b]);
						#endif
						}
				}
				#ifdef DEBUG_3
					printf("F[%d][%d][%d] = %d \n", i, a, b, F[i][a][b]);
				#endif
			}
	fprintf(fout, "%d", F[p-1][nA][nB]);

}

int main()
{
	fin  = fopen(INPUT_FILE, "r");
	fout = fopen(OUTPUT_FILE,"w");
	assert(fin);
	assert(fout);
	if (ReadCase())
		SolveCase();
	fclose(fin);
	fclose(fout);
	return 0;
}