Untitled

 avatar
unknown
plain_text
a year ago
1.6 kB
4
Indexable
#include <iostream>;
using namespace std;
int N,MIN;
int VT[5],SL[5],V[5],A[70];

int Trai(int cua)
{
	int people = SL[cua];
	int vt = VT[cua];
	int j=0;
	int value=0;
	while (people>0)
	{
		if( vt-j >0 && A[vt-j]==0)
		{
			A[vt-j] = cua;
			value+= j+1;
			people--;
		}
		if( vt+j <=N && A[vt+j]==0 && people!=0)
		{
			A[vt+j] = cua;
			value+= j+1;
			people--;
		}
		j++;
	}
	return value;
}

int Phai(int cua)
{
	int people = SL[cua];
	int vt = VT[cua];
	int j=0;
	int value=0;
	while (people>0)
	{
		if( vt+j <=N && A[vt+j]==0)
		{
			A[vt+j] = cua;
			value+= j+1;
			people--;
		}
		if( vt-j >0 && A[vt-j]==0 && people!=0)
		{
			A[vt-j] = cua;
			value+= j+1;
			people--;
		}

		j++;
	}
	return value;
}

void BackTrack(int index, int sum)
{
	if(index == 3)
	{
		//for(int i=0;i<=N;i++) cout<<A[i]<<" ";

		//cout<<MIN<<" "<<sum<<endl;

		if(MIN>sum)
		{
			MIN=sum;
		}
		return;
	}
	for(int i=1;i<=3;i++)
	{
		if(V[i]==0)
		{
			V[i]=1;
			BackTrack(index+1,sum+Trai(i));
			//V[i]=0;
			for(int a=0;a<=N;a++)
			{
				if(A[a]==i)
				{
					A[a]=0;
				}
			}
			BackTrack(index+1, sum+Phai(i));
			V[i]=0;
			for(int a=0;a<=N;a++)
			{
				if(A[a]==i)
				{
					A[a]=0;
				}
			}

		}
	}
}

int main()
{
	freopen("Text.txt","r",stdin);
	int T;
	cin>>T;
	for(int tc=1;tc<=T;tc++)
	{
		cin>>N;
		for(int i=1;i<=3;i++)
		{
			cin>>VT[i]>>SL[i];
			V[i]=0;
		}
	}
	for(int i=0;i<=N;i++)
	{
		A[i]=0;
	}
	MIN=9999;
	BackTrack(0,0);
	cout<<MIN;
	return 0;
}
Editor is loading...
Leave a Comment