连接数

  1 #include<iostream>
  2 using namespace std;
  3 
  4 #define SIZE  9
  5 #define MAXLEN  6
  6 int data[SIZE][MAXLEN];
  7 int numberLen[SIZE];//某一行有几位
  8 int overlapLen[SIZE+1][SIZE+1];//某两位数的重叠长度
  9 int maxLen=0;
 10 int used[SIZE];
 11 
 12 void IToA(int N,int row)//数字转数组，并记录长度
 13 {
 14   int  tmp=N;
 15   int n=0;
 16   while(tmp){   //统计位数
 17     n++;
 18     tmp/=10;
 19   }
 20   numberLen[row]=n;  //位数信息放进数组
 21   tmp=N;
 22   for(int j=n-1;j>=0;j--)
 23   {
 24    data[row][j]=tmp%10;
 25    tmp/=10; 
 26   }
 27 }
 28 
 29 void getOverlapLen(int i,int j)//计算两个数字的最小重叠长度，分前后，i在前，j在后
 30 {
 31   for(int len=1;len<=numberLen[i]&&len<=numberLen[j];len++)//遍历重合长度
 32   {
 33         int flag=1;//标志位
 34         for(int m=numberLen[i]-len,n=0;m<numberLen[i]&&n<numberLen[j];m++,n++)
 35         {
 36               if(data[i][m]!=data[j][n])
 37               {
 38                  flag=0;
 39                  break;
 40               }
 41         }
 42         if(flag)
 43         {
 44               overlapLen[i][j]=len;
 45               break;
 46         }
 47   }
 48 }
 49 
 50 void getMaxLen(int step,int numbers,int curLen,int remainingLen,int preNumber)
 51 {
 52  if(step==numbers)  return ;//出口
 53  if(curLen+remainingLen-(numbers-step)+1<=maxLen)  return;//预测长度剪枝
 54 
 55    for(int i=0;i<numbers;i++)//全排列过程
 56    {
 57       if(!used[i])
 58       {
 59         used[i]=1;
 60         int tmpLen=curLen;
 61 
 62         //关键代码，必须有
 63         if(overlapLen[i][preNumber]==0&&step!=0)//只处理连接成功的情况
 64         {
 65          used[i]=0;//注意占位及恢复
 66          continue;
 67         }
 68 
 69         curLen +=numberLen[i]-overlapLen[i][preNumber];
 70         if(maxLen<curLen) 
 71             maxLen=curLen;
 72         getMaxLen(step+1,numbers,curLen,remainingLen-numberLen[i],i);//全排列的同时进行dfs
 73         used[i]=0;  //数据恢复
 74         curLen=tmpLen;
 75       }
 76    }
 77 }
 78 
 79 int main()
 80 {
 81   freopen("input.txt","r",stdin);
 82   int nTc;
 83   cin>>nTc;
 84   while(nTc--)
 85   {
 86    int N;
 87    cin>>N;
 88    
 89    //全局变量初始化
 90    maxLen=0;
 91    for(int i=0;i<SIZE;i++)
 92    {
 93      used[i]=0;
 94      for(int j=0;j<MAXLEN;j++)   
 95      {
 96         data[i][j]=0;     
 97      }
 98    }
 99    for(int i=0;i<=SIZE;i++)
100    {
101      for(int j=0;j<=SIZE;j++)   
102      { 
103         overlapLen[i][j]=0;
104      }
105    }
106 
107    int temp;  
108    int totalLen=0;//N个数总共有多少位
109    for(int i=0;i<N;i++)
110    {
111      cin>>temp;
112      IToA(temp,i);
113      totalLen+=numberLen[i];
114    }
115 
116     //求重合长度，数据预处理，可以处理极端的case
117     for(int i=0;i<N;i++)
118     {
119          for(int j=0;j<N;j++)
120          {
121              if(i!=j)      
122                  getOverlapLen(i,j);
123          }
124     }
125 
126     getMaxLen(0,N,0,totalLen,SIZE); //step=0时，要求chongdie[i][prenum]=0
127     cout<<maxLen<<endl;
128   }
129   return 0;
130 }