首页 > 代码库 > ADV数字的剪切

ADV数字的剪切

#include <iostream>

using namespace  std;

#define  SIZE 9
#define  MAXLEN  6

int data[SIZE][MAXLEN];
int numberLen[SIZE];
int overlapLen[SIZE+1][SIZE+1];


void IToA(int N ,int row)   //数字转换为数组
{
	int tmp=N;
	int i=0;
	while(tmp)
	{
		i++;
		tmp/=10;
	}
	numberLen[row]=i;
	tmp=N;
	for(int j=i-1;j>=0;j--)
	{
		data[row][j]=tmp%10;
		tmp/=10;
	}
}

void getOverlapLen(int i,int j)  //计算两个数字的最小重叠长度 
{
	for(int len=1;len<=numberLen[i]&&len<=numberLen[j];len++)
	{
		int match=1;
		for(int m=numberLen[i]-len,n=0;m<numberLen[i]&&n<numberLen[j];m++,n++)
		{
			if(data[i][m]!=data[j][n])
			{
				match=0;
				break;
			}
		}

		if(match)
		{
			overlapLen[i][j]=len;
			break;
		}
	}
}

int maxLen=0;
int used[SIZE];

void getMaxLen(int step ,int numbers,int curlen,int remainingLen,int preNumber)
{
	if(step==numbers)
		return ;
	if(curlen+remainingLen-numbers+step+1<=maxLen)
		return;

	for(int i=0;i<numbers;i++)
	{
		if(!used[i])
		{
			used[i]=1;
			int tmpLen=curlen;

			if(overlapLen[i][preNumber]==0&&step!=0)    //连接成功
			{
				used[i]=0;
				continue;
			}	

			curlen+=numberLen[i]-overlapLen[i][preNumber];
			if(maxLen<curlen)
				maxLen=curlen;
			getMaxLen(step+1,numbers,curlen,remainingLen-numberLen[i],i);

			used[i]=0;
			curlen=tmpLen;
			
		}
	}
}

void main()
{
	//freopen("in.txt","r",stdin);
	int nTc;
	cin>>nTc;
	for(int tc=0;tc<nTc;tc++)
	{
		int N;
		cin>>N;
		maxLen=0;
		for(int i=0;i<N;i++)
		{
			used[i]=0;
			for(int j=0;j<N;j++)
			{
				data[i][j]=0;
				overlapLen[i][j]=0;
			}
		}

		int temp;
		int totalLen=0;
		for(int i=0;i<N;i++)
		{
			cin>>temp;
			IToA(temp,i);
			totalLen+=numberLen[i];

		}

		for(int i=0;i<N;i++)
		{
			for(int j=0;j<N;j++)
			{
				if(i!=j)
				getOverlapLen(i,j);
			}
		}

		getMaxLen(0,N,0,totalLen,SIZE);
		cout<<maxLen<<endl;
	}
}

 

ADV数字的剪切