fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define f first
  5. #define s second
  6.  
  7. typedef long long ll; 
  8. typedef pair <int, int> ii; 
  9. typedef pair <char, ll> pll; 
  10.  
  11. const int INF = 0x3f3f3f3f; 
  12. const int N = (int) 25e2 + 5; 
  13.  
  14. vector <pll> decode(string s) {
  15. 	vector <pll> res; 
  16. 	int i = 0; 
  17.  
  18. 	while (i < (int)s.size()) {
  19. 		res.push_back({s[i], 0}); 
  20.  
  21. 		i++; 
  22.  
  23. 		while (i < (int)s.size()) {
  24. 			if (isdigit(s[i])) 
  25. 				res.back().s = res.back().s * 10 + s[i] - '0'; 
  26. 			else 
  27. 				break; 
  28.  
  29. 			i++; 
  30. 		}
  31. 	}
  32.  
  33. 	return res; 
  34. }
  35.  
  36. ll f[N][N]; 
  37. ll pre_x[N][26], pre_y[N][26]; 
  38. ll prev_x[N][26], prev_y[N][26]; 
  39.  
  40. bool check(int i, int j, int cur_i, int cur_j, char c) {
  41. 	int cnt_x = pre_x[cur_i][c - 'a'] - pre_x[i][c - 'a']; 
  42. 	int cnt_y = pre_y[cur_j][c - 'a'] - pre_y[j][c - 'a']; 
  43.  
  44. 	return (cnt_x <= cnt_y); 
  45. }
  46.  
  47. ii find(vector <pll> x, vector <pll> y, int cur_i, int cur_j, char c) {
  48. 	ii res = {0, 0};
  49.  
  50. 	for (int i = cur_i - 1; i >= 1; i--) {
  51. 		int j = prev_y[cur_j][x[i - 1].f - 'a']; 
  52.  
  53. 		if (j == INF) break; 
  54.  
  55. 		if (check(i, j, cur_i, cur_j, c)) {
  56. 			res = {i, j}; 
  57.  
  58. 			return res; 
  59. 		}		   	
  60. 	} 
  61.  
  62. 	for (int j = cur_j - 1; j >= 1; j--) {
  63. 		int i = prev_x[cur_i][y[j - 1].f - 'a']; 
  64.  
  65. 		if (i == INF) break; 
  66.  
  67. 		if (!check(i, j, cur_i, cur_j, c)) {
  68. 			res = {i, j}; 
  69.  
  70. 			return res; 
  71. 		}
  72. 	}
  73.  
  74. 	return res; 
  75. }
  76.  
  77. void precompute(vector <pll> x, vector <pll> y, int n, int m) {
  78. 	for (char c = 'a'; c <= 'z'; c++) {
  79. 		for (int i = 0; i < n; i++)
  80. 			pre_x[i + 1][c - 'a'] = pre_x[i][c - 'a'] + (x[i].f == c ? x[i].s : 0);   
  81.  
  82. 		for (int j = 0; j < m; j++) 
  83. 			pre_y[j + 1][c - 'a'] = pre_y[j][c - 'a'] + (y[j].f == c ? y[j].s : 0); 
  84. 	}
  85.  
  86. 	memset(prev_x, INF, sizeof prev_x); 
  87. 	memset(prev_y, INF, sizeof prev_y); 
  88.  
  89. 	for (int i = 1; i <= n; i++) {
  90. 		for (char c = 'a'; c <= 'z'; c++) {
  91. 			prev_x[i][c - 'a'] = prev_x[i - 1][c - 'a']; 
  92.  
  93. 			prev_x[i + 1][x[i - 1].f - 'a'] = i; 
  94. 		}
  95. 	}
  96.  
  97. 	for (int i = 1; i <= m; i++) {
  98. 		for (char c = 'a'; c <= 'z'; c++) {
  99. 			prev_y[i][c - 'a'] = prev_y[i - 1][c - 'a']; 
  100.  
  101. 			prev_y[i + 1][y[i - 1].f - 'a'] = i; 
  102. 		}
  103. 	}
  104. }
  105.  
  106. ll LCS1(vector <pll> x, vector <pll> y) {
  107. 	int n = (int)x.size(); 
  108. 	int m = (int)y.size(); 
  109.  
  110. 	precompute(x, y, n, m); 
  111.  
  112. 	for (int i = 1; i <= n; i++) {
  113. 		for (int j = 1; j <= m; j++) {
  114. 			if (x[i - 1].f == y[j - 1].f) {
  115. 				char c = x[i - 1].f; 
  116.  
  117. 				ii pos = find(x, y, i, j, c); 
  118.  
  119. 				ll cnt_x = pre_x[i][c - 'a'] - pre_x[pos.f][c - 'a'];
  120. 				ll cnt_y = pre_y[j][c - 'a'] - pre_y[pos.s][c - 'a']; 
  121.  
  122. 				f[i][j] = f[pos.f][pos.s] + min(cnt_x, cnt_y);  
  123. 			}
  124. 		}
  125. 	}
  126.  
  127. 	return f[n][m];  
  128. }
  129.  
  130. ll g[N][N]; 
  131.  
  132. ll LCS2(vector <pll> x, vector <pll> y) {
  133. 	int n = (int)x.size(); 
  134. 	int m = (int)y.size(); 
  135.  
  136. 	for (int i = 1; i <= n; i++) {
  137. 		for (int j = 1; j <= m; j++) {
  138. 			if (x[i - 1].f != y[j - 1].f) 
  139. 				g[i][j] = 0; 
  140. 			else 
  141. 				g[i][j] = min(x[i - 1].s, y[j - 1].s) + g[i - 1][j - 1]; 
  142. 		}
  143. 	}	
  144.  
  145. 	ll ans = 0; 
  146. 	for (int i = 1; i <= n; i++) {
  147. 		for (int j = 1; j <= m; j++) ans = max(ans, g[i][j]); 
  148. 	}
  149.  
  150. 	return ans; 
  151. }
  152.  
  153. int main() {
  154. 	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  155. 	string a, b; 
  156. 	cin >> a >> b; 
  157.  
  158. 	vector <pll> x = decode(a); 
  159. 	vector <pll> y = decode(b); 
  160.  
  161. 	cout << LCS1(x, y) << "\n"; 
  162. 	cout << LCS2(x, y) << "\n"; 
  163. }
  164.  
Success #stdin #stdout 0.01s 7604KB
comments (?)
stdin
copy 
a4b2
c2b1
stdout
copy 
1
1
https://ideone.com/zz6dVJ
language:
C++14 (gcc 8.3)
created:
2 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!