2041520_ce.cc

北大大牛代码 1240道题的原代码 超级权威

# include <math.h>
# include <stdio.h>
# include <string.h>
# define max(a,b) a>b?a:b
# define min(a,b) a<b?a:b
# define MAX 2100000000

int N;
int a[10001];
long L, D;
long DP[100001];
long LDP[100001];
long left;
long right;
long lleft;
long lright;

void get_pos(int i,int l)
{
	if(l)
	{
		left = max(i*D,L-(N-1-i)*(D+1));
		right = min(i*(D+1),L-(N-1-i)*D);
	}
	else
	{
		lleft = max(i*D,L-(N-1-i)*(D+1));
		lright = min(i*(D+1),L-(N-1-i)*D);
	}
}

void swap(long *a,long *b)
{
	long i;
	long tmp;

	for(i = 0; i <= L; i++)
	{
		tmp = a[i];
		a[i] = b[i];
		b[i] = tmp;
	}
}

void dp()
{
	long i, j;

	memset(DP,0,sizeof(DP));
	memset(LDP,0,sizeof(LDP));
	DP[0] = a[0];
	for(i = 1; i < N; i++)
	{
		swap(DP,LDP);
		get_pos(i,1);
		get_pos(i-1,0);
		for(j = left; j <= right; j++)
		{
			DP[j] = MAX;
			if(j-D-1>=lleft)
				DP[j] = min(DP[j],LDP[j-D-1]);
			if(j-D<=lright)
				DP[j] = min(DP[j],LDP[j-D]);
			DP[j] += abs(a[i]-j);
		}
	}
	printf("%ld\n",DP[L]);
}

/*void init()
{
	int i;
	long l1, l2, r1, r2;

	for(i = 0; i < N; i++)
	{
		l1 = i*D;
		l2 = i*(D+1);
		r1 = L-(N-1-i)*(D+1);
		r2 = L-(N-1-i)*D;
		pos[i].left = max(l1,r1);
		pos[i].right = min(l2,r2);
	}
}*/

void input()
{
	int i;

	scanf("%d%ld",&N,&L);
	D = L/(N-1);
	for(i = 0; i < N; i++)
		scanf("%d",&a[i]);
}

int main()
{
	input();
	//init();
	dp();
	return 1;
}