3115.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:3115  User Id:fzk 
Memory:24K  Time:93MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

int main( ) {
	__int64 m[4][2], *ans = m[0], *temp = m[1], *id = m[2], *idt = m[3], s1, s2, 
		mem[2][20], *res = mem[0], *rest = mem[1];
	int en[20], ti[20];
	int f, p, e, a, i, j;

	while( 1 ) {
		scanf( "%d%d%d%d", &f, &p, &e, &a );
		e *= a;
		if( f == 0 && p == 0 && e == 0 && a == 0 ) break;

		ans[0] = 0;
		ans[1] = 50000000000;
		id[0] = 0;
		id[1] = 1;

		for( j=0; j<f; j++ )
			res[j] = 50000000000;

		for( i=0; i<p; i++ ) {
			for( j=0; j<f; j++ ) {
				scanf( "%d%d", en+j, ti+j );
				en[j] *= ti[j];
			}

			temp[0] = 50000000000;
			temp[1] = 50000000000;

			for( j=0; j<f; j++ ) {
				s1 = ans[0] + en[j] + e*(j!=id[0]);
				s2 = ans[1] + en[j] + e*(j!=id[1]);
				rest[j] = res[j] + en[j];

				if( s1 < rest[j] ) rest[j] = s1;
				if( s2 < rest[j] ) rest[j] = s2;

				if( rest[j] < temp[0] ) {
					temp[1] = temp[0], idt[1] = idt[0];
					temp[0] = rest[j], idt[0] = j;
				}
				else if( rest[j] < temp[1] )
					temp[1] = rest[j], idt[1] = j;
			}

			swap( temp, ans );
			swap( id, idt );
			swap( rest, res );
		}

		printf( "%I64d\n", ans[0] );
	}
	return 0;
}