首页 > 代码库 > 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数字的剪切
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。