1993902_tle.c

北大大牛代码 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 30000

int N;
int a[10001];
long L, D;
int DP[100001];
int LDP[100001];

struct node
{
	long left;
	long right;
}pos[100001];

void swap(int *a,int *b)
{
	long i;
	int 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);
		for(j = pos[i].left; j <= pos[i].right; j++)
		{
			DP[j] = MAX;
			if(j-D-1>=pos[i-1].left)
				DP[j] = min(DP[j],LDP[j-D-1]);
			if(j-D<=pos[i-1].right)
				DP[j] = min(DP[j],LDP[j-D]);
			DP[j] += abs(a[i]-j);
		}
	}
	printf("%d\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;
}