1013 great equipment.cpp

这是一道经典的DP题目

#include<iostream>
#include<cstring>
using namespace std;

int N;
int w1, s1, d1,
	w2, s2, d2,
	w3, s3, d3,
	c1, c2, c3, d4;
int w[ 110 ], s[ 110 ];
const int MAX = 500;
int d[ 2 ][ 505 ][ 505 ];

inline int min( int a, int b ) {	return a < b ? a : b;	}
inline int max( int a, int b ) {	return a > b ? a : b;	}
inline int compute( int a, int b, int c )
{
	int x = min( a / c1, min( b / c2, c / c3 ) );
	int r = d4 * x + ( a - c1 * x ) * d1 + ( b - c2 * x ) * d2 + ( c - c3 * x ) * d3;

	return r;
}

void read()
{
	scanf( "%d %d %d", &w1, &s1, &d1 );
	scanf( "%d %d %d", &w2, &s2, &d2 );
	scanf( "%d %d %d", &w3, &s3, &d3 );
	scanf( "%d %d %d %d", &c1, &c2, &c3, &d4 );

	for ( int i = 1; i <= N; i ++ )
		scanf( "%d %d", &w[ i ], &s[ i ] );
}

int solve()
{
	d[ 0 ][ 0 ][ 0 ] = 0;
	int i, j, k;
	int jMax = 0, kMax = 0;
	for ( i = 1; i <= N; i ++ )
	{
		memset( d[ 1 ], 0xff, sizeof( d[ 1 ] ) );
		int jM = 0, kM = 0;
		for ( j = 0; j <= jMax; j ++ )
			for ( k = 0; k <= kMax; k ++ )
			{
				if ( d[ 0 ][ j ][ k ] != -1 )
				{
					int q1 = min( w[ i ] / w1, s[ i ] / s1 );
					
					for ( int x = 0; x <= q1; x ++ )
						for ( int y = 0; x * w1 + y * w2 <= w[ i ] && x * s1 + y * s2 <= s[ i ]; y ++ )
						{ 
							int remain = min( ( w[ i ] - x * w1 - y * w2 ) / w3, ( s[ i ] - x * s1 - y * s2 ) / s3 );
							d[ 1 ][ j + x ][ k + y ] = max( d[ 1 ][ j + x ][ k + y ], d[ 0 ][ j ][ k ] + remain );

							if ( j + x > jM )
								jM = j + x;
							if ( k + y > kM )
								kM = k + y;
						}
				}
			}

		jMax = jM; kMax = kM;
		memcpy( d[ 0 ], d[ 1 ], sizeof( d[ 1 ] ) );
	}

	int result = -1;
	for ( j = 0; j <= jMax; j ++ )
		for ( k = 0; k <= kMax; k ++ )
			if ( d[ 1 ][ j ][ k ] != -1 )
				result = max( result, compute( j, k, d[ 1 ][ j ][ k ] ) );
	
	return result;
}

int main()
{
	int i = 0;
	while ( scanf( "%d", &N ) != EOF && N )
	{
		read();

		if ( i )
			printf( "\n" );

		printf( "Case %d: %d\n", ++i, solve() );
	}

	return 0;
}

/*
cout << endl << "test" << endl;
		cout << w1 << " " << w2 << " " << w3 << endl;

		for ( int i = 1; i <= N; i ++ )
			printf( "%d %d\n", w[ i ], s[ i ] );

memset( d, 0xff, sizeof( d ) );

		cout << d[ 0 ][ 0 ][0] << d[1][2][3] << endl;
*/