Xây dựng thuật toán tính tích của dãy số gồm N phần tử

Full PDF PackageDownload Full PDF Package

This Paper

A short summary of this paper

37 Full PDFs related to this paper

Download

PDF Pack

Tác giả: Lê Anh Đức - A2K42-PBC

Quy hoạch động [QHĐ] là một lớp thuật toán rất quan trọng và có nhiều ứng dụng trong ngành khoa học máy tính. Trong các cuộc thi Olympic tin học hiện đại, QHĐ luôn là một trong những chủ đề chính. Tuy vậy, theo tôi thấy, tài liệu nâng cao về QHĐ bằng tiếng Việt hiện còn cực kỳ khan hiếm, dẫn đến học sinh/sinh viên Việt Nam bị hạn chế khả năng tiếp cận với những kỹ thuật hiện đại. Trong bài viết này, tôi sẽ trình bày một vài kỹ thuật để tối ưu hóa độ phức tạp của một số thuật toán QHĐ.

1. Đổi biến

Nhiều khi trong trạng thái QHĐ có một thành phần nào đấy với khoảng giá trị quá lớn, trong khi kết quả của hàm lại có khoảng giá trị nhỏ. Trong một vài trường hợp, ta có thể đảo nhãn để giảm số trạng thái.

Bài tập ví dụ

Longest Common Subsequence [LCS]

Đề bài

Cho xâu A độ dài m, xâu B độ dài n. Hãy tìm độ dài xâu con chung dài nhất của hai xâu, chú ý là xâu con chung có thể không liên tiếp.

Giới hạn

• $m \le 10^6$
• $n \le 5000$
• Các kí tự trong cả hai xâu là các chữ cái tiếng Anh in hoa 'A'..'Z'

Ví dụ

A = ADBCC B = ABCD LCS = ABC Kết quả = 3

Lời giải

Thuật toán đơn giản

Gọi $F[i, j]$ là LCS của hai tiền tố $A_{1..i}$ và $B_{1..j}$.

Khi đó ta có thể maximize $F[i, j]$ theo $F[i-1, j]$ và $F[i, j-1]$.

Nếu $A_i = B_j$ thì ta có thể cập nhật $F[i, j]$ theo $F[i-1, j-1] + 1$.

Kết quả bài toán là $F[m, n]$.

Độ phức tạp của thuật toán này là $O[m*n]$, không khả thi với giới hạn của đề bài.

Đổi biến

Đặt $L = min[m, n]$

Để ý rằng trong hàm QHĐ trên, các giá trị của $F[i, j]$ sẽ không vượt quá $L$, trong khi đó chiều thứ hai của trạng thái có thể khá lớn [lên tới $MAXM = 10^6$].

Để tối ưu hóa, ta sẽ đổi biến. Gọi $dp[i, j]$ là vị trí $k$ nhỏ nhất sao cho $LCS[A_{1..i}, B_{1..k}] = j$.

Để tính các giá trị của $dp$, ta sẽ QHĐ theo kiểu cập nhật đi, thay vì đi tìm công thức trực tiếp cho các $dp[i, j]$.

Gọi $nextPos[i, c] = j > i$ nhỏ nhất mà $A_j = c$ [với $c$ là một ký tự từ 'A' đến 'Z'].

Mảng $nextPos$ có thể tính trong $T[M*26]$.

Như vậy ta có thể tính các giá trị QHĐ như sau:

• Ban đầu khởi tạo các giá trị $dp[i, j] = \infty$, $dp[0, 0] = 0$.
• For $i$ và $j$ tăng dần, với mỗi giá trị $dp[i, j]$ khác vô cùng:
  • Cập nhật $dp[i+1, j]$ theo $dp[i, j]$.
  • Gọi $k$ là vị trí xuất hiện tiếp theo của $B_{i+1}$ trong xâu $A$ bắt đầu từ vị trí $dp[i, j]$, tức là $k = nextPos[dp[i, j], B_{i+1}]$.
  • Nếu tồn tại $k$, cập nhật $dp[i+1, j+1]$ theo $k$.

Để tính kết quả, ta sẽ chỉ cần tìm $j$ lớn nhất mà tồn tại $dp[i, j]$ khác vô cùng.

#include using namespace std; const int M = 1e6 + 6; const int N = 5005; int dp[N][N]; char a[M], b[N]; int nextPos[M][26]; int m, n; void minimize[int &a, int b] { if [a == -1 || a > b] a = b; } int main[] { cin >> a + 1 >> b + 1; m = strlen[a + 1]; n = strlen[b + 1]; for [int c = 0; c = 0; --i] nextPos[i][c] = [a[i + 1] - 'A' == c] ? i + 1 : nextPos[i + 1][c]; int maxLength = min[m, n]; memset[dp, -1, sizeof dp]; dp[0][0] = 0; for [int i = 0; i 0] minimize[dp[i + 1][j + 1], new_value]; } } int ans = 0; for [int j = maxLength; j > 0; --j] { for [int i = j; i = 0] ans = j; if [ans != 0] break; } cout n; cout a >> y >> b >> n; cout 1; best[mid] = from; for [int i = from + 1; i eval[mid + 1, i]] best[mid] = i; solve[L, mid - 1, from, best[mid]]; solve[mid + 1, R, best[mid], to]; }

Đánh giá độ phức tạp thuật toán: vì mỗi lần gọi để quy khoảng $[L,R]$ được chia đôi, nên sẽ có $O[logN]$ tầng, mỗi tầng vòng for chỉ chạy qua $O[N]$ phần tử, vì vậy độ phức tạp của thuật toán là $O[NlogN]$.

SEQPART - Hackerrank

Đề bài

Cho dãy $L$ số $C[1..L]$, cần chia dãy này thành $G$ đoạn liên tiếp. Với phần tử thứ $i$, ta định nghĩa chi phí của nó là tích của $C[i]$ và số lượng số nằm cùng đoạn liên tiếp với nó. Chi phí của dãy số ứng với một cách phân hoạch là tổng các chi phí của các phần tử.

Hãy xác định cách phân hoạch dãy số để chi phí là nhỏ nhất.

Input

• Dòng đầu tiên chứa 2 số $L$ và $G$.
• $L$ dòng tiếp theo, chứa giá trị của dãy $C$.

Output

• Một dòng duy nhất chứa chi phí nhỏ nhất.

Giới hạn

• $1 \le L \le 8000$.
• $1 \le G \le 800$.
• $1 \le C[i] \le 10^9$.

Ví dụ

Input 6 3 11 11 11 24 26 100 Output 299

Giải thích: cách tối ưu là $C[] = [11, 11, 11], [24, 26], [100]$.

Chi phí là $11 * 3 + 11 * 3 + 11 * 3 + 24 * 2 + 26 * 2 + 100 * 1 = 299$.

Lời giải

Đây là dạng bài toán phân hoạch dãy số có thể dễ dàng giải bài QHĐ. Gọi $F[g, i]$ là chi phí nhỏ nhất nếu ta phân hoạch $i$ phần tử đầu tiên thành $g$ nhóm, khi đó kết quả bài toán sẽ là $F[G, L]$.

Để tìm công thức truy hồi cho hàm $F[g, i]$, ta sẽ quan tâm đến nhóm cuối cùng. Coi phần tử 0 là phần tử cầm canh ở trước phần tử thứ nhất, thì người cuối cùng không thuộc nhóm cuối có chỉ số trong đoạn $[0, i]$. Giả sử đó là người với chỉ số k, thì chi phí của cách phân hoạch sẽ là $F[g-1, k] + Cost[k+1, i]$, với $Cost[i, j]$ là chi phí nếu phân $j-i+1$ người có chỉ số $[i, j]$ vào một nhóm. Như vậy:

$F[g, i] = min[F[g-1, k] + Cost[k+1, l]]$ với $0 > L >> G; for [int i = 1; i > C[i]; sum[i] = sum[i - 1] + C[i]; } for [int g = 1; g > G; for [int i = 1; i > C[i]; sum[i] = sum[i - 1] + C[i]; } for [int i = 1; i