3042.txt

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

Problem Id:3042  User Id:fzk 
Memory:15744K  Time:153MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <algorithm>
#include <memory.h>

int x[1001];
__int64 ans[1001][1001][2];

int main() {
	int i, j, n, k;
	scanf( "%d%d", &n, &k );
	
	for( i=0; i<n; i++ ) {
		scanf( "%d", &x[i] );
	}

	x[n] = k;

	std::sort( x, x+n+1 );
	for( i=0; i<=n; i++ )
		if( x[i] == k ) {
			k = i;
			break;
		}

	memset( ans, 0x7f, sizeof ans );
	ans[k][k][0] = ans[k][k][1] = 0;

	for( i=k; i>=0; i-- )
	for( j=k; j<=n; j++ ) {
		if( i ) {
			if( ans[i-1][j][0] > ans[i][j][0] + (x[i]-x[i-1])*(i+n-j) )
				ans[i-1][j][0] = ans[i][j][0] + (x[i]-x[i-1])*(i+n-j);
			if(ans[i-1][j][0] > ans[i][j][1] + (x[j]-x[i-1])*(i+n-j) )
				ans[i-1][j][0] = ans[i][j][1] + (x[j]-x[i-1])*(i+n-j);
		}
		if( j < n ) {
			if( ans[i][j+1][1] > ans[i][j][0] + (x[j+1]-x[i])*(i+n-j) )
				ans[i][j+1][1] = ans[i][j][0] + (x[j+1]-x[i])*(i+n-j);
			if( ans[i][j+1][1] > ans[i][j][1] + (x[j+1]-x[j])*(i+n-j) )
				ans[i][j+1][1] = ans[i][j][1] + (x[j+1]-x[j])*(i+n-j);
		}
	}

	k = ans[0][n][0];
	if( k > ans[0][n][1] )
		k = ans[0][n][1];
	printf( "%d\n", k );

	return 0;
}