Source Code

Problem: 1682  User: yzhw 
Memory: 836K  Time: 813MS 
Language: G++  Result: Accepted 

Source Code 
# include <cstdio>
# include <cstring>
# include <iostream>
using namespace std;
# define N 105
int dp1[N][N],dp2[N][N],dp3[N][N];
int h[3][N];
int n,m,k;
# define abs(a) ((a)<0?-(a):(a))
# define min(a,b) ((a)<(b)?(a):(b))
int solve1(int p1,int p2)
{
	if(dp1[p1][p2]!=-1) return dp1[p1][p2];
	else if(p1==0&&p2==k-1) return dp1[p1][p2]=abs(h[0][p1]-h[2][p2]);
	else if(!p1) return dp1[p1][p2]=solve1(p1,p2+1)+abs(h[0][p1]-h[2][p2]);
	else if(p2==k-1) return dp1[p1][p2]=solve1(p1-1,p2)+abs(h[0][p1]-h[2][p2]);
	else return dp1[p1][p2]=min(solve1(p1-1,p2+1),min(solve1(p1,p2+1),solve1(p1-1,p2)))+abs(h[0][p1]-h[2][p2]);
}
int solve2(int p1,int p2)
{
	if(dp2[p1][p2]!=-1) return dp2[p1][p2];
	else if(p1==n-1&&p2==0) return dp2[p1][p2]=abs(h[0][p1]-h[1][p2]);
	else if(p1==n-1) return dp2[p1][p2]=solve2(p1,p2-1)+abs(h[0][p1]-h[1][p2]);
	else if(!p2) return dp2[p1][p2]=solve2(p1+1,p2)+abs(h[0][p1]-h[1][p2]);
	else return dp2[p1][p2]=min(solve2(p1+1,p2-1),min(solve2(p1+1,p2),solve2(p1,p2-1)))+abs(h[0][p1]-h[1][p2]);
}
int solve3(int p1,int p2)
{
	if(dp3[p1][p2]!=-1) return dp3[p1][p2];
	else if(p1==m-1&&!p2) return dp3[p1][p2]=abs(h[1][p1]-h[2][p2]);
	else if(p1==m-1) return dp3[p1][p2]=solve3(p1,p2-1)+abs(h[1][p1]-h[2][p2]);
	else if(!p2) return dp3[p1][p2]=solve3(p1+1,p2)+abs(h[1][p1]-h[2][p2]);
	else return dp3[p1][p2]=min(solve3(p1+1,p2-1),min(solve3(p1,p2-1),solve3(p1+1,p2)))+abs(h[1][p1]-h[2][p2]);
}
int main()
{
	int test;
	scanf("%d",&test);
	while(test--)
	{
		int i;
		scanf("%d%d%d",&n,&m,&k);
		for(i=0;i<n;i++)
			scanf("%d",&h[0][i]);
		for(i=0;i<m;i++)
			scanf("%d",&h[1][i]);
		for(i=0;i<k;i++)
			scanf("%d",&h[2][i]);
		int ans=0xfffffff;
		memset(dp1,-1,sizeof(dp1));
		memset(dp2,-1,sizeof(dp2));
		memset(dp3,-1,sizeof(dp3));
		for(i=0;i<n;i++)
		{
			ans=min(ans,solve1(i,0)+solve2(i,m-1));
			if(i!=n-1)
				ans=min(ans,solve1(i,0)+solve2(i+1,m-1));
		}
		for(i=0;i<k;i++)
		{
			ans=min(ans,solve1(n-1,i)+solve3(0,i));
			if(i!=k-1)
				ans=min(ans,solve1(n-1,i+1)+solve3(0,i));
		}
		for(i=0;i<m;i++)
		{
			ans=min(ans,solve2(0,i)+solve3(i,k-1));
			if(i!=m-1)
				ans=min(ans,solve2(0,i)+solve3(i+1,k-1));
		}
		int p1,p2,p3,p4,p5,p6;
		for(p1=0;p1<n;p1++)
			for(p2=p1;p2<=p1+1&&p2<n;p2++)
				for(p3=0;p3<m;p3++)
					for(p4=p3;p4<=p3+1&&p4<m;p4++)
						for(p5=0;p5<k;p5++)
							for(p6=p5;p6<=p5+1&&p6<k;p6++)
								ans=min(ans,solve1(p1,p6)+solve2(p2,p3)+solve3(p4,p5));
		printf("%d\n",ans);
	}
	return 0;
}