Bình luận

• 
  

  25

  SPyofgame    7:20 p.m. 29 Tháng 4, 2021 ← đã chỉnh sửa →

  Thi thử duyên hải 2021 lần hai bài CPU

• 
  

  23

  SPyofgame    7:49 p.m. 29 Tháng 4, 2021 ← chỉnh sửa 2 →

  ---

  \(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

  \(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

  \(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

  ---

  ---

  \(\color{orange}{\text{Hướng dẫn}}\)

  • Gọi cách chia \(X\) là chia \(2n\) chương trình thành \(n\) cặp \((A_1, B_1), (A_2, B_2), \dots, (A_n, B_n)\)

  Gọi thời gian xử lí của một cặp \((A_i, B_i)\) là \(f(A_i, B_i)\)

  Thời gian xử lí toàn bộ chương trình cách chia \(P\) là \(g(X) = max(f(A_i, B_i))\)

  Yêu cầu bài toán là tìm \(res = min(g(X)) = min(max(f(A_i, B_i)))\) [1]

  • Với mỗi cặp \((A, B)\)

  Từ [1] ta có \(f(A, B)\) càng nhỏ càng tốt, nên ta phải tìm cách để xử lí 2 chương trình một cách tối ưu

  Khi phát xung nhịp, gọi \(a\) là kí tự đầu của \(A\) và \(b\) là kí tự đầu của \(B\)

  Khi \(a = b\) thì ta loại cả \(a\) và \(b\) cùng lúc và tăng một đơn vị thời gian

  Khi \(a \neq b\) thì ta sẽ thử loại một trong hai và tăng một đơn vị thời gian

  ---

  \(\color{goldenrod}{\text{Tiếp cận}}\)

  • Để xử lí cặp \((A, B)\), ta dùng quy hoạch động đếm

  Xét \(f(i, j)\) là thời gian nhỏ nhất để loại bỏ \(A[i \dots n]\) và \(B[j \dots m]\) với \(n = |A|\) và \(m = |B|\)

  Khi \(A_i = B_j\) thì \(f(i, j) = f(i + 1, j + 1) + 1\)

  Khi \(A_i \neq B_i\) thì \(f(i, j) = min(f(i + 1, j), f(i, j + 1)) + 1\)

  • Để xử lí \(res = min(max(f(A_i, B_i)))\), ta dùng quy hoạch động trạng thái

  Vì \(2n\) nhỏ, xét \(2^{2n}\) trạng thái \(S\) đánh dấu các chương trình đã được ghép cặp

  Khi xét tới chương trình thứ \(i\) chưa được ghép cặp, ta thử xét trong \(2n\) chương trình còn lại có cái nào chưa ghép cặp ta ghép luôn

  \(g(i, S) = min\Bigg(\ max\bigg(\ g(i + 1, S\ \cup\) {\(\ j\ \(}\)\ )\ \ ,\ \ f(A_i, A_j)\ \bigg)\ \Bigg)\)

  • Khi đó kết quả bài toán sẽ là \(res = min(g(i, S))\)

  ---

  \(\color{purple}{\text{Độ phức tạp}}\)

  • Với cách đề cập trên

  Có tất cả \(O(n \times 2^{2n})\) giá trị \(g(i, S)\) cần duyệt qua để tính \(res\)

  Hàm \(g(i, S)\) chuyển trạng thái mất \(|S| \times f(i, j) = 2n \times |A_i| \times |A_j|\)

  Vậy độ phức tạp rơi vào khoảng \(O(2n^2 \times 2^{2n} \times max(|A_i|)^2)\)

  Có thể coi là \(O(2^{2n})\) với hằng số cao

  • Tối ưu

  Ta truyền bitmask thay vì tập đánh dấu

  Ta sẽ tiền xử lí tính toán trước các giá trị \(f(i, j)\)

  Ta sẽ luôn ghép cặp từ thằng \(i\) với các thằng khác, nên biến \(i\) là không quan trọng, vì với mọi \(S\) bất kì ta có thểm tìm được \(i\) tương ứng

  Độ phức tạp lúc này chỉ còn \(O(n^2 \times max(|A_i|)^2 + 2^{2n})\)

  ---

  \(\color{green}{\text{Code tham khảo }}\): Approach

  \(^{^{\color{purple}{\text{Độ phức tạp : }} O(2^{2n})\ \color{purple}{\text{thời gian}}\ ||\ O(2^{2n})\ \color{purple}{\text{bộ nhớ}}}}\)

  C++

  const int INF = 0x3f3f3f3f;
  const int LIM = 111;
  
  int n, k;
  string a[111];
  int cost[111][111];
  
  string u, v;
  int f[111][111];
  
  /// Solve for each pair
  int calc(int i = 0, int j = 0)
  {
      if (i >= u.size()) return int(v.size()) - j; /// da xoa het (u), con lai (|v| - j) ki tu cua (v)
      if (j >= v.size()) return int(u.size()) - i; /// tuong tu nhu tren
  
      int &res = f[i][j];
      if (res != -1) return res;
      res = +INF;
  
      res = min(calc(i + 1, j), calc(i, j + 1)) + 1;
      if (u[i] == v[j])
          minimize(res, calc(i + 1, j + 1) + 1);
  
      return res;
  }
  
  int g[1 << 22];
  /// Solve for all pairs
  int solve(int i = 1, int mask = 0)
  {
      if (i > n) return 0;
      if (mask >> i & 1) return solve(i + 1, mask);
  
      int &res = g[mask];
      if (res != -1) return res;
      res = +INF;
  
      for (int j = i + 1; j <= n; ++j)
      {
          if (mask >> j & 1) continue; /// (j) is used
          minimize(res, max(solve(i + 1, mask | (1 << j)), cost[i][j]));
      }
  
      return res;
  }
  
  int main()
  {
      /// Input
      cin >> n;
      k = 1 * n;
      n = 2 * n;
      for (int i = 1; i <= n; ++i)
          cin >> a[i];
  
      /// Precalculating
      for (int i = 1; i <= n; ++i)
      {
          for (int j = i + 1; j <= n; ++j)
          {
              u = a[i];
              v = a[j];
              memset(f, -1, sizeof(f));
              cost[i][j] = cost[j][i] = calc();
          }
      }
  
      /// Solving
      memset(g, -1, sizeof(g));
      cout << solve();
      return 0;
  }
  
4 bình luận nữa