2430.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

 

#include"iostream.h"
#include"algorithm"

const int size=1010;
int ans[size][size][4];
int best[size][size];

int n,m,b,nn;
enum{both,up,down,sep};
const int inf=99999999;

struct point
{
	int y;
	int x;
	int s;
}pt[size],p[size];

bool cmp(point a,point b)
{
	return a.x<b.x;
}

void init()
{
	int i,j;
	cin>>n>>m>>b;
	
	for(i=0;i<n;i++)
	{
		cin>>pt[i].y>>pt[i].x;
		pt[i].s=0;
	}

	std::sort(pt,pt+n,cmp);
	
	p[0].x=p[0].y=0;
	p[1]=pt[0];
	for(i=1,j=2;i<n;i++)	
	{
		if(pt[i].x==pt[i-1].x)
			p[j-1].s=1;
		else p[j++]=pt[i];
	}
	nn=n;
	n=j;
	
}

void doit()
{
	int i,j,t,k;
	
	for(j=0;j<=m;j++)
	{
		for(k=0;k<4;k++)
			ans[0][0][k]=0;
		best[0][j]=0;
	}

	for(i=1;i<n;i++)
	{
		for(k=0;k<4;k++)
			ans[i][0][k]=inf;
		best[i][0]=inf;

		for(j=1;j<=m;j++)
		{
			ans[i][j][up]=ans[i][j][down]=best[i-1][j-1]+1;
			if(p[i].y==p[i-1].y && (t=ans[i-1][j][p[i].y]+p[i].x-p[i-1].x) < ans[i][j][p[i].y] )
				ans[i][j][p[i].y] = t;
			if( (t=ans[i-1][j][sep]+p[i].x-p[i-1].x) < ans[i][j][p[i].y] )
				ans[i][j][p[i].y] = t;

			ans[i][j][both]=best[i-1][j-1]+2;
			if( (t=ans[i-1][j][both]+(p[i].x-p[i-1].x)*2) <ans[i][j][both] )
				ans[i][j][both] = t;

			if(j==1)ans[i][j][sep]=inf;
			else
			{
				ans[i][j][sep]=best[i-1][j-2]+2;
				if( (t=ans[i-1][j-1][up]+p[i].x-p[i-1].x+1) < ans[i][j][sep] )
					ans[i][j][sep] = t;
				if( (t=ans[i-1][j-1][down]+p[i].x-p[i-1].x+1) < ans[i][j][sep] )
					ans[i][j][sep] = t;
				if( (t=ans[i-1][j][sep]+(p[i].x-p[i-1].x)*2 ) < ans[i][j][sep] )
					ans[i][j][sep] = t;
			}
	
			if(p[i].s)
				ans[i][j][up]=ans[i][j][down]=inf;
			else
				ans[i][j][3-p[i].y]=inf;

			best[i][j]=inf;
			for(k=0;k<4;k++)
				if(ans[i][j][k]<best[i][j])
					best[i][j]=ans[i][j][k];
		}
	}
}
int main()
{
	init();
	doit();
	
	cout<<best[n-1][m]<<endl;

	return 0;
}