首页 > 代码库 > poj1699
poj1699
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 char data[11][101]; 5 int len[11]; 6 int addlen[11][11]; 7 int minnum; 8 int used[11]; 9 void add(int x,int y); 10 void dfs(int pre,int step,int sum,int num); 11 int main() 12 { 13 /*freopen("in.txt","r",stdin);*/ 14 int n,m; 15 cin >>n; 16 for(int i=0;i<n;i++) 17 { 18 minnum=10000; 19 cin >>m; 20 for(int j=0;j<m;j++) 21 { 22 cin >>data[j]; 23 len[j]=strlen(data[j]); 24 used[j]=0; 25 } 26 for(int j=0;j<m;j++) 27 for(int k=0;k<m;k++) 28 add(j,k); 29 for(int j=0;j<m;j++) 30 { 31 used[j]=1; 32 dfs(j,1,len[j],m); 33 used[j]=0; 34 } 35 cout <<minnum<<endl; 36 37 38 } 39 return 0; 40 } 41 void dfs(int pre,int step,int sum,int num) 42 { 43 if(sum>=minnum) return; 44 if(step==num) 45 { 46 if(sum<minnum) 47 minnum=sum; 48 return; 49 } 50 for(int i=0;i<num;i++) 51 { 52 if(used[i]==0) 53 { 54 used[i]=1; 55 dfs(i,step+1,sum+addlen[pre][i],num); 56 used[i]=0; 57 } 58 } 59 } 60 61 62 63 64 void add(int x,int y) 65 { 66 int length=0; 67 for(int i=1;i<=len[x]&&i<=len[y];i++) 68 { 69 bool flag=true; 70 for(int j=len[x]-i,k=0;k<i;k++,j++) 71 { 72 if(data[x][j]!=data[y][k]) 73 { 74 flag=false; 75 break; 76 } 77 } 78 if(flag) 79 length=i; 80 } 81 //cout <<length<<" "; 82 addlen[x][y]=len[y]-length; 83 }
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 char data[11][101]; 5 int len[11]; 6 int addlen[11][11]; 7 int minnum; 8 int used[11]; 9 void add(int x,int y); 10 void dfs(int pre,int step,int sum,int num); 11 int main() 12 { 13 /*freopen("in.txt","r",stdin);*/ 14 int n,m; 15 cin >>n; 16 for(int i=0;i<n;i++) 17 { 18 minnum=10000; 19 cin >>m; 20 for(int j=0;j<m;j++) 21 { 22 cin >>data[j]; 23 len[j]=strlen(data[j]); 24 used[j]=0; 25 } 26 for(int j=0;j<m;j++) 27 for(int k=0;k<m;k++) 28 add(j,k); 29 for(int j=0;j<m;j++) 30 { 31 used[j]=1; 32 dfs(j,1,len[j],m); 33 used[j]=0; 34 } 35 cout <<minnum<<endl; 36 37 38 } 39 return 0; 40 } 41 void dfs(int pre,int step,int sum,int num) 42 { 43 if(sum>=minnum) return; 44 if(step==num) 45 { 46 if(sum<minnum) 47 minnum=sum; 48 return; 49 } 50 for(int i=0;i<num;i++) 51 { 52 if(used[i]==0) 53 { 54 used[i]=1; 55 dfs(i,step+1,sum+addlen[pre][i],num); 56 used[i]=0; 57 } 58 } 59 } 60 61 62 63 64 void add(int x,int y) 65 { 66 int length=0; 67 for(int i=1;i<=len[x]&&i<=len[y];i++) 68 { 69 bool flag=true; 70 for(int j=len[x]-i,k=0;k<i;k++,j++) 71 { 72 if(data[x][j]!=data[y][k]) 73 { 74 flag=false; 75 break; 76 } 77 } 78 if(flag) 79 length=i; 80 } 81 //cout <<length<<" "; 82 addlen[x][y]=len[y]-length; 83 }
poj1699
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。