2492607_ac_312ms_1008k.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);
	}
}

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

void dp()
{
	int i, j;
	int *DD, *LL;

	memset(DP,0,sizeof(DP));
	memset(LDP,0,sizeof(LDP));
	DP[0] = a[0];
	DD = DP,LL = LDP;
	for(i = 1; i < N; i++)
	{
		if(DD==DP)
		{
			DD = LDP;
			LL = DP;
		}
		else
		{
			DD = DP;
			LL = LDP;
		}
		get_pos(i,1);
		get_pos(i-1,0);
		for(j = left; j <= right; j++)
		{
			DD[j] = MAX;
			if(j-D-1>=lleft)
				DD[j] = min(DD[j],LL[j-D-1]);
			if(j-D<=lright)
				DD[j] = min(DD[j],LL[j-D]);
			DD[j] += Abs(a[i]-j);
		}
	}
	printf("%d\n",DD[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;
}