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. // - Bài toán "loại bỏ ít phần tử nhất" <=> Bài toán "chọn nhiều phần tử nhất"
  12. // - Nhận xét: Khi xét đến b[i], ta chỉ cần quan tâm tới các b[j] sao cho b[i] - b[j] <= 9 
  13. //             <=> b(j) >= b(i) - 9 
  14. // - Do đó, nếu mảng b đã được sort và chỉ chứa các giá trị phân biệt,
  15. //   thì khi xét đến b[i], ta chỉ cần quan tâm đến tối đa 9 phần tử liền trước nó.  
  16. template<typename T>
  17. void maximize(T& a, const T& b) {
  18. 	if (a < b) a = b;  
  19. }
  20.  
  21. const int N = 2e3 + 5; 
  22.  
  23. int n; 
  24. int b[N]; 
  25. int cnt[N]; // cnt[i] = Số lần xuất hiện của b[i]
  26. int dp[N][1 << 9]; // dp[i][mask] = Độ dài dãy con SEQ198 dài nhất khi xét i phần tử đầu tiên, 
  27. 				   //               với mask biểu diễn các phần tử được chọn trong 9 phần tử gần i nhất (bao gồm cả i)    
  28.  
  29. bool check(int i, int prev_mask) {
  30. 	for (int k = 0; k < 9; k++) {
  31. 		if ((prev_mask >> k) & 1) {
  32. 			int j = i - 1 - k;  
  33. 			if (j < 1) continue; 
  34. 			int d = b[i] - b[j]; 
  35. 			if (d == 1 || d == 8 || d == 9) return false; 
  36. 		}
  37. 	}
  38. 	return true; 
  39. }
  40.  
  41. int main() {
  42. 	ios::sync_with_stdio(false); 
  43. 	cin.tie(nullptr); 	
  44. 	cin >> n; 
  45. 	for (int i = 1; i <= n; i++) cin >> b[i];
  46.  
  47. 	sort(b + 1, b + n + 1); 
  48. 	int m = 0;   
  49. 	int cur = -1;  
  50. 	for (int i = 1; i <= n; i++) {
  51. 		if (b[i] == cur) {
  52. 			++cnt[m]; 
  53. 		}
  54. 		else {
  55. 			++m;  
  56. 			b[m] = b[i]; 
  57. 			cnt[m] = 1; 
  58. 			cur = b[i]; 
  59. 		}
  60. 	}  
  61.  
  62. 	for (int i = 0; i <= m; i++) {
  63. 		for (int mask = 0; mask < (1 << 9); mask++) dp[i][mask] = -INF; 
  64. 	}
  65. 	dp[0][0] = 0;  
  66.  
  67. 	for (int i = 1; i <= m; i++) {
  68. 		for (int prev_mask = 0; prev_mask < (1 << 9); prev_mask++) {
  69. 			int mask = (prev_mask << 1) & 511; 
  70. 			// Không chọn b[i]
  71. 			maximize(dp[i][mask], dp[i - 1][prev_mask]);
  72. 			// Chọn b[i]
  73. 			if (check(i, prev_mask)) maximize(dp[i][mask | 1], dp[i - 1][prev_mask] + cnt[i]); 
  74. 		}
  75. 	}
  76.  
  77. 	int ans = 0;   
  78. 	for (int mask = 0; mask < (1 << 9); mask++) {
  79. 		maximize(ans, dp[m][mask]); 
  80. 	}
  81. 	ans = n - ans;  
  82.  
  83. 	cout << ans << '\n'; 
  84. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
5
7 3 1 9 21
stdout
copy 
1
https://ideone.com/E1ogWc
language:
C++14 (gcc 8.3)
created:
13 days 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!