fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. // Hàm Hash tùy chỉnh để lưu trạng thái mảng vào unordered_map
  9. struct VectorHasher {
  10.     size_t operator()(const vector<long long>& V) const {
  11.         size_t hash = V.size();
  12.         for (long long i : V) {
  13.             hash ^= i + 0x9e3779b9 + (hash << 6) + (hash >> 2);
  14.         }
  15.         return hash;
  16.     }
  17. };
  18.  
  19. int n;
  20. unordered_map<vector<long long>, int, VectorHasher> memo;
  21.  
  22. int dfs(vector<long long>& a) {
  23.     // Điều kiện dừng: Tất cả phần tử đã về 0
  24.     bool all_zero = true;
  25.     for (long long x : a) {
  26.         if (x != 0) {
  27.             all_zero = false;
  28.             break;
  29.         }
  30.     }
  31.     if (all_zero) return 0;
  32.  
  33.     // Trả về kết quả nếu đã tính toán
  34.     if (memo.count(a)) return memo[a];
  35.  
  36.     int ans = 1e9;
  37.  
  38.     // Duyệt qua tất cả các đoạn con dài nhất (maximal intervals) có cùng tính chẵn lẻ
  39.     for (int i = 0; i < n; ) {
  40.         int j = i;
  41.         int parity = a[i] & 1;
  42.         bool has_nonzero = false;
  43.  
  44.         // Mở rộng đoạn [i, j) xa nhất có thể
  45.         while (j < n && (a[j] & 1) == parity) {
  46.             if (a[j] != 0) has_nonzero = true;
  47.             j++;
  48.         }
  49.  
  50.         // Chỉ chia đôi nếu đoạn này có ít nhất 1 phần tử khác 0
  51.         if (has_nonzero) {
  52.             vector<long long> nxt = a;
  53.             for (int k = i; k < j; ++k) {
  54.                 nxt[k] >>= 1;
  55.             }
  56.             // Đệ quy tìm số bước tối thiểu
  57.             ans = min(ans, 1 + dfs(nxt));
  58.         }
  59.  
  60.         // Chuyển sang đoạn tiếp theo
  61.         i = j;
  62.     }
  63.  
  64.     return memo[a] = ans;
  65. }
  66.  
  67. void solve() {
  68.     cin >> n;
  69.     vector<long long> a(n);
  70.     for (int i = 0; i < n; ++i) {
  71.         cin >> a[i];
  72.     }
  73.  
  74.     // Reset bảng nhớ cho mỗi testcase
  75.     memo.clear();
  76.     cout << dfs(a) << "\n";
  77. }
  78.  
  79. int main() {
  80.     // Tối ưu I/O
  81.     ios_base::sync_with_stdio(false);
  82.     cin.tie(NULL);
  83.  
  84.     int t;
  85.     if (cin >> t) {
  86.         while (t--) {
  87.             solve();
  88.         }
  89.     }
  90.     return 0;
  91. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
4
2
9 12
3
3 1 2
1
0
7
6 28 24 18 12 22 1
stdout
copy 
5
3
0
10
https://ideone.com/2O9gtp
language:
C++14 (gcc 8.3)
created:
52 minutes 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!