2492488_tle.cc

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

# 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];
int L, D, DP[100001], LDP[100001], left, right, lleft, 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(int *a,int *b)
{
	int i;
	int tmp;

	int *tt;

	tt = a;
	a = b;
	b = tt;
	for(i = 0; i <= L; i++)
	{
		tmp = *(a+i);
		*(a+i) = *(b+i);
		*(b+i) = tmp;
	}
}

int Abs(int num)
{
	return num*(num<0?-1:1);
}

void dp()
{
	int 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("%d\n",DP[L]);
}

void input()
{
	int i;

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

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