3184.txt

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

Source

Problem Id:3184  User Id:fzk 
Memory:148K  Time:295MS
Language:G++  Result:Accepted

Source 

#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <memory.h>
using namespace std;

int l[10000];
int temp[2][10001], *ans1 = temp[0], *ans2 = temp[1];

int main( ) {
	int n, len, i, j, d1, d2, rest, t, k, *ans_i_j, *ans_i1_j;

	scanf( "%d%d", &n, &len );

	for( i=0; i<n; i++ )
		scanf( "%d", l+i );

	d1 = len/(n-1);
	d2 = d1 + (len%(n-1)?1:0);
	rest = len - d1*(n-1);

	ans1[0] = l[0]+1;

	for( i=0; i<n-1; i++ ) {
		
		j = 0;

		if( n-1-i<rest )
			j = rest-(n-1-i);

		ans_i_j = &ans1[j];
		ans_i1_j = &ans2[j];
		k = (i-j)*d1+j*d2-l[i+1];
		*ans_i1_j = 0;

		for( ; j<=i && j<=rest; j++ ) {
			if( *ans_i_j ) {
				t = *ans_i_j + abs( k+d1 );

				if( !*ans_i1_j || *ans_i1_j > t )
					*ans_i1_j = t;

				ans_i1_j++;
				if( j < rest ) {
					*ans_i1_j = *ans_i_j + abs( k+d2 );
				}
			}
			else {
				ans_i1_j++;
				*ans_i1_j = 0;
			}

			ans_i_j++;
			k += d2-d1;
		}
		swap( ans1, ans2 );
	}

	printf( "%d\n", ans1[rest]-1 );
	return 0;
}