记录编号	29984	评测结果	WWWAWWAWWA
题目名称	388.抢修道路	最终得分	30
用户昵称	TBK	是否通过	未通过
代码语言	C++	运行时间	0.047 s
提交时间	2011-10-27 09:17:59	内存使用	0.32 MiB

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;      
int a[2001][3]={0},b[2001][3]={0},c,d,l,m,n,s1=0,s2=0,t,x,y,z;
bool bo1[2001]={false},bo2[2001]={false};
int ab(int k)
{
	if (k<0) return 0-k;
		else return k;
}
int main(void)      
{         
    freopen("roady.in","r",stdin);      
    freopen("roady.out","w",stdout);       
    scanf("%d",&n);   
    for (c=0;c<n;c++) 
	{
		scanf("%d",&a[c][0]);
		b[c][0]=a[c][0];
	}
	for (d=0;d<n;d++) a[d][1]=-1;
	for (d=1;d<n;d++)   
		for (l=d-1;l>=0;l--)   
			if ((a[d][0]>=a[l][0])&&(a[l][2]>=a[d][2]))
			{
				a[d][1]=l;
				a[d][2]=a[l][2]+1;
			}
	x=0;
	for (d=0;d<n;d++) 
		if (a[d][2]>x) x=a[d][2];
	for (d=0;d<n;d++) b[d][1]=-1;
	for (d=1;d<n;d++)   
		for (l=d-1;l>=0;l--)   
			if ((b[d][0]<=b[l][0])&&(b[l][2]>=b[d][2])) 
			{
				b[d][1]=l; 
				b[d][2]=b[l][2]+1;
			}
	y=0;
	for (d=0;d<n;d++)
		if (b[d][2]>y) y=b[d][2];
	for (d=0;d<n;d++)
		if (a[d][2]==x) break;
	t=a[d][1];
	bo1[d]=true;
	while (t!=-1)
	{
		bo1[t]=true;
		t=a[t][1];
	}
	for (d=0;d<n;d++)
		if (bo1[d]==false)
		{
			if ((d!=0)&&(d!=n-1)) 
			{
				if (ab(a[d][0]-a[d-1][0])>ab(a[d][0]-a[d+1][0])) s1+=ab(a[d][0]-a[d+1][0]);
					else s1+=ab(a[d][0]-a[d-1][0]);
			}
				else if (d==0) s1+=ab(a[0][0]-a[1][0]);
						else s1+=ab(a[n-2][0]-a[n-1][0]);
		}
	for (d=0;d<n;d++)
		if (b[d][2]==x) break;
	t=b[d][1];
	bo2[d]=true;
	while (t!=-1)
	{
		bo2[t]=true;
		t=b[t][1];
	}	
	for (d=0;d<n;d++)
		if (bo2[d]==false)
		{
			if ((d!=0)&&(d!=n-1)) 
			{
				if (ab(b[d][0]-b[d-1][0])>ab(b[d][0]-b[d+1][0])) s2+=ab(b[d][0]-b[d+1][0]);
					else s2+=ab(b[d][0]-b[d-1][0]);
			}
				else if (d==0) s2+=ab(b[0][0]-b[1][0]);
					else s2+=ab(b[n-2][0]-b[n-1][0]);
		}
	if (s1<s2) printf("%d\n",s1);
		else printf("%d\n",s2);
    fclose(stdin);
	fclose(stdout);
    return 0;      
}