fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. template<typename T>
  12. void maximize(T& a, const T& b) {
  13. 	if (a < b) a = b;  
  14. }
  15.  
  16. const int N = 15e2 + 5; 
  17.  
  18. int n, m; 
  19. int a[N], b[N]; 
  20.  
  21. int dp[N][N]; // dp[i][j] = Độ dài dãy con chung bội hai dài nhất của a[1..i] và b[1..j] và b[j] chắc chắn được chọn 
  22.  
  23. void solve() {
  24. 	cin >> n >> m; 
  25. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  26. 	for (int i = 1; i <= m; i++) cin >> b[i]; 
  27.  
  28. 	memset(dp, 0, sizeof dp);  
  29.  
  30. 	// O(n * m^2)
  31. 	// for (int i = 1; i <= n; i++) {
  32. 	// 	for (int j = 1; j <= m; j++) {
  33. 	// 		// b[j] không bắt cặp với a[i]
  34. 	// 		dp[i][j] = dp[i - 1][j]; 
  35.  
  36. 	// 		// b[j] bắt cặp với a[i]
  37. 	// 		if (b[j] == a[i]) {
  38. 	// 			dp[i][j] = 1;  
  39. 	// 			for (int prev_j = 1; prev_j < j; prev_j++) {
  40. 	// 				if (2 * b[prev_j] <= b[j]) {
  41. 	// 					maximize(dp[i][j], dp[i - 1][prev_j] + 1); 
  42. 	// 				}
  43. 	// 			}
  44. 	// 		}
  45. 	// 	}
  46. 	// }
  47.  
  48. 	// O(n * m)
  49. 	for (int i = 1; i <= n; i++) {
  50. 		int opt_j = -1;   
  51.  
  52. 		for (int j = 1; j <= m; j++) {
  53. 			// b[j] không bắt cặp với a[i]
  54. 			dp[i][j] = dp[i - 1][j]; 
  55.  
  56. 			// b[j] bắt cặp với a[i]
  57. 			if (b[j] == a[i]) {
  58. 				dp[i][j] = 1; 
  59. 				if (opt_j != -1) maximize(dp[i][j], dp[i - 1][opt_j] + 1); 
  60. 			}
  61.  
  62. 			// cập nhật điểm j' tối ưu
  63. 			if (2 * b[j] <= a[i]) {
  64. 				if (opt_j == -1 || dp[i - 1][opt_j] < dp[i - 1][j]) opt_j = j; 
  65. 			}
  66. 		}
  67. 	}
  68.  
  69. 	int ans = 0;   
  70. 	for (int j = 1; j <= m; j++) {
  71. 		maximize(ans, dp[n][j]); 
  72. 	}
  73.  
  74. 	cout << ans << '\n'; 
  75. }
  76.  
  77. int main() {
  78. 	ios::sync_with_stdio(false); 
  79. 	cin.tie(nullptr); 	
  80. 	int T; cin >> T;  
  81.  
  82. 	while (T--) {
  83. 		solve();  
  84. 	}
  85. }
  86.  
Success #stdin #stdout 0.01s 12500KB
comments (?)
stdin
copy 
1
5 5
5 1 6 10 20
1 8 6 10 20
stdout
copy 
3
https://ideone.com/TJVdjg
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!