1829.txt

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

#include <stdio.h>
#include <memory.h>
#include <algorithm>
int ans[1025][161], s[1025];
int v[161], n, m;
const int MAX = ( (unsigned int)1<<31-1 );
void clac( ) {
	int i, j, k, t, h, best;	
	memset( ans, 0x7F, sizeof ans );	
	ans[1][1] = v[1];
	s[1] = v[1];
	for( i=2; i<=n; i++ ) {
		for( j=2; j<=i&&j<=m; j++ ) {
			best = ans[i-1][j-1]+v[j];
			h = i/j;
			if( h > i-j+1 )
				h = i-j+1;
			for( k=2; k<=h; k++ )
				if( ( t = ans[i-k][j-1] + s[k] + v[j]*k*k ) < best )
					best = t;
			ans[i][j] = best;
		}
		best = MAX;
		for( j=2; j<=i&&j<=n; j++ )
			if( ans[i][j] < best )
				best = ans[i][j];
		s[i] = best;
		ans[i][1] = s[i] + v[1]*i*i;
	}

}
int main( ){
	int t, i;
	scanf( "%d", &t );
	while( t-- ) {
		scanf( "%d %d", &n, &m );
		for( i=1; i<=m; i++ )
			scanf( "%d", &v[i] );
		std::sort( v+1, v+m+1 );
		clac( );
		printf( "%d\n", s[n] );
	}
	return 0;
}