fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <map>
  4. using namespace std;
  5. const int inf = 0x3f3f3f3f;
  6. const int maxn = 200 + 100;
  7. const int maxm = 2000 + 100;
  8. int g[maxn][maxn], pre[maxm][maxm], match[maxn], matched[maxn], a[maxm], b[maxm];
  9. long long f[maxm][maxm];
  10. char base[maxn], ta[maxm], tb[maxm], ans1[maxm * 2], ans2[maxm * 2];
  11. map<char, int> ap;
  12. int main() {
  13. 	scanf("%s%s%s", base, ta, tb);
  14. 	int l = strlen(base), la = strlen(ta), lb = strlen(tb);
  15. 	for(int i = 0; i < l; ++i) {
  16. 		ap[base[i]] = i;
  17. 	}
  18. 	for(int i = 0; i < la; ++i) {
  19. 		a[i] = ap[ta[i]];
  20. 	}
  21. 	for(int i = 0; i < lb; ++i) {
  22. 		b[i] = ap[tb[i]];
  23. 	}
  24. 	for(int i = 0; i < l; ++i) {
  25. 		for(int j = 0; j < l; ++j) {
  26. 			scanf("%d", &g[i][j]);
  27. 			if(g[i][j] < g[i][match[i]]) {
  28. 				match[i] = j;
  29. 			}
  30. 			if(g[i][j] < g[matched[j]][j]) {
  31. 				matched[j] = i;
  32. 			}
  33. 		}
  34. 	}
  35. 	f[0][0] = 0;
  36. 	pre[0][0] = -1;
  37. 	for(int i = 0; i < la; ++i) {
  38. 		f[i + 1][0] = f[i][0] + g[a[i]][match[a[i]]];
  39. 		pre[i + 1][0] = 0;
  40. 	}
  41. 	for(int i = 0; i < lb; ++i) {
  42. 		f[0][i + 1] = f[0][i] + g[matched[b[i]]][b[i]];
  43. 		pre[0][i + 1] = 1;
  44. 	}
  45. 	for(int i = 0; i < la; ++i) {
  46. 		for(int j = 0; j < lb; ++j) {
  47. 			if(f[i][j + 1] + g[a[i]][match[a[i]]] < f[i + 1][j] + g[matched[b[j]]][b[j]]) {
  48. 				f[i + 1][j + 1] = f[i][j + 1] + g[a[i]][match[a[i]]];
  49. 				pre[i + 1][j + 1] = 0;
  50. 			} else {
  51. 				f[i + 1][j + 1] = f[i + 1][j] + g[matched[b[j]]][b[j]];
  52. 				pre[i + 1][j + 1] = 1;
  53. 			}
  54. 			if(f[i][j] + g[a[i]][b[j]] < f[i + 1][j + 1]) {
  55. 				f[i + 1][j + 1] = f[i][j] + g[a[i]][b[j]];
  56. 				pre[i + 1][j + 1] = 2;
  57. 			}
  58. 		}
  59. 	}
  60. 	printf("%lld\n", f[la][lb]);
  61. 	int lans;
  62. 	for(lans = 0; pre[la][lb] != -1; ++lans) {
  63. 		if(pre[la][lb] == 2) {
  64. 			--la, --lb;
  65. 			ans1[lans] = base[a[la]];
  66. 			ans2[lans] = base[b[lb]];
  67. 		} else if(pre[la][lb] == 0) {
  68. 			--la;
  69. 			ans1[lans] = base[a[la]];
  70. 			ans2[lans] = base[match[a[la]]];
  71. 		} else if(pre[la][lb] == 1) {
  72. 			--lb;
  73. 			ans1[lans] = base[matched[b[lb]]];
  74. 			ans2[lans] = base[b[lb]];
  75. 		}
  76. 	}
  77. 	--lans;
  78. 	for(int i = lans; 0 <= i; --i) {
  79. 		putchar(ans1[i]);
  80. 	}
  81. 	puts("");
  82. 	for(int i = lans; 0 <= i; --i) {
  83. 		putchar(ans2[i]);
  84. 	}
  85. 	puts("");
  86. }
  87.  
Success #stdin #stdout 0s 55368KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/q6r9SH
SGU 214. Weird Dissimilarity
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!