Advertisement
Guest User

Untitled

a guest
Feb 20th, 2020
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.62 KB | None | 0 0
  1. #include <stdio.h>
  2. int a[11][11];
  3. char b[11][100];
  4. int c[11];
  5. int min = 10000000;
  6. int o[11];
  7. int v;
  8. void prefix1(int i, int j) {
  9. int y,x;
  10. for(int m = 1;m<c[i];m++) {
  11. y = 0;
  12. x = m;
  13. while((b[i][x] == b[j][y]) && (y <= c[j] - 1) && (x < c[i])) {
  14. ++y;
  15. ++x;
  16. }
  17. if (x == c[i]) {
  18. a[i][j] = c[i]-m;
  19. break;
  20. }
  21. }
  22. }
  23. void rec(int k,int dlin,int kol) {
  24. int flag = 0;
  25. if (kol == v) {
  26. if (dlin < min) {
  27. min = dlin;
  28. }
  29. }
  30. else {
  31. for(int j = 0;j<v;j++) {
  32. o[kol-1] = k;
  33. for(int l = 0;l<=kol-1;l++) {
  34. if (o[l] == j) {
  35. flag = 1;
  36. break;
  37. }
  38. }
  39. if (flag != 1) {
  40. rec(j , dlin+c[j]-a[k][j] , kol+1);
  41. }
  42. flag = 0;
  43. }
  44. }
  45. }
  46. int main()
  47. {
  48. scanf("%d\n" , &v);
  49. int y = getchar();
  50. int t = 0,l = 0;
  51. while(y !=EOF) {
  52. if (y != 10) {
  53. b[t][l] = y;
  54. ++l;
  55. }
  56. else {
  57. c[t] = l;
  58. ++t;
  59. l = 0;
  60. }
  61. y = getchar();
  62. }
  63. c[t] = l;
  64. for(int i =0;i<v;i++) {
  65. for(int j =0;j<v;j++) {
  66. a[i][j] = 0;
  67. if (i != j ) {
  68. prefix1(i,j);
  69. }
  70. }
  71. }
  72. if (v == 1) {
  73. printf("%d" , c[0]);
  74. }
  75. else {
  76. for(int i = 0;i<v;i++) {
  77. rec(i , c[i] , 1);
  78. }
  79. }
  80. printf("%d" , min);
  81. return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement