Sáng kiến kinh nghiệm Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học

cout.tie(0); 
 freopen("FIRSTROW.inp","r",stdin); 
 freopen("FIRSTROW.out","w",stdout); 
 for(i=0;i<255;i++)a[i]=0; 
 while (getline(cin,s)) 
 { 
 for(i=0;i<s.length();i++) a[i]^=int(s[i]); 
 } 
for(i=0;i<255;i++)cout<<char(a[i]); 
} 
Bài toán 10. Dãy số 
Với số nguyên không âm X bất kì, bạn có thể tạo dãy số A[X] như sau: 
 Số đầu tiên của dãy là X. 
 Sau một số lẻ y sẽ là số y – 1. 
 Sau một số chẵn y sẽ là số y / 2. 
Ví dụ với X = 60. Ta có dãy số 60, 30, 15, 14, 7,  
Cho K, A, B nhiệm vụ của bạn là đếm xem có bao nhiêu số nguyên X trong 
đoạn từ A đến B mà dãy A[X] chứa K. 
Dữ liệu vào: Trong file văn bản NEXT.INP Gồm một dòng duy nhất ghi 3 
số K, A, B ( tất cả các số đều không âm và không quá 1018, A ≤ B). 
Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học 
Trang 22 
Kết quả ra: Ra file văn bản NEXT.OUT Ghi ra kết quả tìm được. 
Input Output 
3 4 8 2 
1 23457 123456 100000 
13 12345 67890123 8387584 
Lời giải: Nếu K = 0, kết quả là B – A + 1. 
 Gọi các số X mà trong A[X] có K là các số tạo K. 
 Trong trường hợp K >= 1. Các số tạo K sẽ có phần nhị phân đầu tiên giốn K 
hoặc K + 1 trong trường hợp K chẵn. 
 Ví dụ nếu K = 1012 thì các số tạo K phải có dạng 101x2 với x có thể rỗng 
hoặc là một xâu nhị phân. Nếu K chẵn, ví dụ K = 1002 thì các số tạo K có dạng 
100x2 hoặc 101x2 
 Ta sẽ đếm các số này theo số lượng bit. Giả sử K có L bít, như vậy các số 
tạo K có L bit sẽ nằm trong đoạn [C, D] với [C, D] bằng [K, K] nếu K lẻ và [K, K 
+ 1] nếu K chẵn. Các số tạo K có L + 1 bít sẽ nằm trong đoạn [C × 2, D × 2 + 1], 
các số tạo K có L + 2 bít sẽ nằm trong đoạn [C × 2 × 2, (D × 2 + 1) × 2 + 1]. Tìm 
giao của các đoạn này với đoạn [A, B] sẽ ra số lượng số cần tìm. 
#include 
using namespace std; 
#define bit(x, i) (x >> i) & 1 
void cass() 
{ 
 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
 freopen("next.inp", "r", stdin); 
 freopen("next.out", "w", stdout); 
} 
long long k, a, b; 
int main() 
{ 
Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học 
Trang 23 
 cass(); 
 cin >> k >> a >> b; 
 if (k==0) {cout << b - a + 1; return 0;} 
 long long l, r; 
 if (k & 1) l = r = k; else { l = k; r = k + 1;} 
 long long res = 0; 
 int cs1, cs2; 
 for (int i = 0; i < 64; ++i) { 
 if (bit(k, i)) cs1 = i; 
 if (bit(b, i)) cs2 = i; 
 } 
 int x=cs2-cs1; 
 while (x>=0){ 
 long long tmp; 
 if (a > r || l > b) tmp = 0; 
 else { 
 long long mama = min(r, b), mimi = max(a, l); 
 tmp = max(mama - mimi + 1, 0LL); 
 } 
 res = res + tmp; 
 l = l * 2; r = r * 2 + 1; 
 x--; 
 } 
 cout << res; 
} 
Bài toán 11: Đầu bếp 
Một đầu bếp đang chuẩn bị một bữa ăn với N nguyên liệu (N < 20). Vị đầu 
bếp muốn bữa ăn phải có đầy đủ K chất (K < 20) C1, C2, , Ck. Để vấn đề dễ hiểu, 
Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học 
Trang 24 
ta chưa quan tâm đến lượng của các chất trong bữa ăn. Với mỗi nguyên liệu ta biết 
được nó có chứa chất nào trong thành phần của nó. Đầu bếp muốn biết tất cả các 
tập nguyên liệu mà tập đó chứa đầy đủ K chất. 
Dữ liệu: 
Dòng 1: N và K 
N dòng tiếp theo: mỗi dòng chứa K số thể hiện thành phần của mỗi nguyên 
liệu, số thứ i thể hiện nó có chứa chất Ci hay ko, là 1 nếu nó chứa chất Ci, 0 ngược 
lại. 
Chẳng hạn: 
6 7 
1 0 0 1 0 1 0 
0 1 0 0 1 0 0 
1 0 0 0 0 0 1 
0 0 1 1 0 0 0 
1 1 0 0 0 0 0 
0 0 0 0 0 1 0 
Đầu bếp có 6 nguyên liệu, và ông ta quan tâm bữa ăn phải chứa đủ 7 chất. 
Nguyên liệu thứ nhất chỉ chứa chất C1, C4, C6 
Giải quyết: 
Với mỗi nguyên liệu, nó sẽ có trạng thái là được chọn hoặc không được 
chọn. Mỗi nguyên liệu có 2 trạng thái, vậy sẽ có tất cả 2^N trạng thái cho N 
nguyên liệu. Với những trường hợp N nhỏ thì duyệt qua tất cả các trạng thái là 
chuyện dễ dàng (2^20 ~ 10^6). Cách duyệt qua tất cả các phương án để tìm lời giải 
gọi là duyệt trâu bò. Vấn đề là thể hiện cách duyệt qua tất cả trạng thái bằng ngôn 
ngữ lập trình. Bạn có thể dùng đệ qui để giải quyết, nó vẫn ok. Tuy nhiên, mình 
muốn trình bày bằng bitmask, code ngắn, dễ sử dụng lại. 
Do có 2^N trạng thái, tất cả trạng thái là 0000002=0, 0000012=1, 
0000102=2, , 1111112=2^N-1. Tất cả trạng thái là các số nguên chạy từ 0 đến 
2^N-1. Nên chỉ với một vòng lặp for(state=0; state < 2^N; state++) đã biểu diễn 
được việc “duyệt qua tất cả trạng thái“ 
Với mỗi giá trị của state, ta muốn biết nguyên liệu thứ i có được chọn hay 
ko, ta chỉ cần xét biểu thức (state and 2^i), i tính từ 0 đến K-1. Nếu biểu thức này 
Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học 
Trang 25 
lớn hơn 0 nghĩa là nguyên liệu thứ i được chọn trong trạng thái state, ngược lại thì 
0. and ở đây là phép and bit.(Bạn tự kiểm chứng biểu thức này). 
Một điểm chú ý nữa, Với mỗi nguyên liệu thứ i ta cũng chuyển thành một số 
b[i] để diễn tả thành phần của nó. Ví dụ với nguyên liệu thứ nhất, ta sẽ biểu diễn 
b[0] = 10010102=74. 
Như vậy nếu các nguyên liệu được chọn có các giá trị b[i] or với nhau hợp 
thành 11111112=(2^K-1) thì tập đó thỏa mãn. or ở đây là phép or bit 
For(state=0; state < 2^N; state++) 
{ 
 Sumarize = 0; 
 For(i=0; i 0) 
{ 
 Sumarize = Sumarize or b[i]; 
 } 
 If(Sumarize == (2^K-1)) 
{ 
 //Print the result 
 } 
} 
Độ phức tạp của đoạn code trên là O(2^N*K), với N=K=20 thì chạy trong 1s 
là ok. 
Bài toán 12: Biểu diễn trạng thái. 
Với bài toán 10, chúng ta chỉ biểu diễn không hoặc có. Thực tế kĩ thuật này 
được hiểu xa hơn một tí, ta xét ví dụ khá quen thuộc sau: 
Ta có ba chai nước có thể tích là V1, V2, V3 (Vi < 10) (đơn vị thể tích). Ban 
đầu ta có chai nước thứ nhất đầy nước và hai chai còn lại không chứa gì cả. Bạn 
cần tìm cách rót sao cho bình V3 chứa K (K<=V3) thể tích nước và số lần rót là ít 
nhất. Bạn được thực hiện một trong các cách sau: 
1. Rót hết nước từ chai này sang chai khác (được phép tràn) 
Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học 
Trang 26 
2. Rót nước từ chai này sang chai khác cho đến lúc chai khác được nhận đầy 
nước. 
3. Rót bỏ hết nước từ một chai. 
Với mỗi trạng thái (x1, x2, x3) thì ta cũng có thể dùng dãy 3 phần tử để diễn tả 
chúng. Tuy nhiên ta cũng có thể diễn tả trạng thái của ba chai bằng một số nguyên 
X= (x1*(V2+1)+x2)*(V3+1)+x3. Bạn có thắc mắc tại sao nhân với V2+1 và V3+1. 
Thật ra nhân với số lớn hơn 2 số này vẫn thỏa, hai số này là hai số nhỏ nhất có 
thể nhân vào, dựa vào tính chất của phép mod. Với cách diễn đạt này, thì đảm bảo 
với mỗi bộ số (x1, x2, x3) khác nhau thì X cũng khác nhau (bạn tự kiểm tra bằng 
phản chứng). Với mỗi số nguyên X biểu diễn cho một thái, ta có thể biết được 
lượng nước trong mỗi chai 
- x1 = X / ((V2+1)(V3+1)) 
- x2 = (X/(V3+1)) mod (V2 +1) 
- x3 = X mod (V3+1) 
Tổng cộng ta có (V1+1)*(V2+1)*(V3+1) trạng thái, ta cũng biết được quy tắc 
chuyển từ trạng thái này sang trạng thái khác thông qua các cách rót nước. 
Ta xây dựng một đồ thị có (V1+1)*(V2+1)*(V3+1) đỉnh, xây dựng các cạnh 
nối bằng các quy tắc của đề bài. Trạng thái bắt đầu là (V1, 0 ,0), số nguyên biểu 
diễn là V1*(V2+1)*(V3+1). Trạng thái kết thúc là (0, 0, K), số nguyên biểu diễn là 
K. 
Có đồ thị, việc tìm đường đi ngắn nhất từ đỉnh này đến đỉnh khác là dễ dàng 
thông qua các giải thuật có sẵn. Với bài này ta có thể dùng breadth first search 
hoặc dijkstra. Ở đây ta không chú tâm đến việc giải bài này, ta chỉ tìm hiểu cách 
tiếp cận biểu diễn trạng thái bằng một số nguyên. 
Bài toán 13: Quy hoạch động 
Bài toán tìm đường đi Hamilton là một bài toán khá quen thuộc: cho N đỉnh, 
tìm đường đi sao cho mỗi đỉnh được thăm duy nhất một lần, và chi phí thăm N 
đỉnh là thấp nhất. 
Với bài toán này, thông thường nếu N nhỏ (N <=10), ta có thể giải quyết bài 
toán bằng phương pháp nhánh cận. Tuỳ vào cách đặt cận mà tốc độ chương trình 
có thể được nâng lên, tuy nhiên thời gian chạy chương trình vẫn có thể không đảm 
bảo với một số test khó. 
Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học 
Trang 27 
Không những vậy, nếu giới hạn N tăng lên đến 20, thì việc sử dụng phương 
pháp nhánh cận để giải quyết sẽ không còn khả thi nữa. Trong trường hợp này, ta 
có cách tiếp cận khác để giải quyết bài toán một cách hiệu quả hơn, với độ phức 
tạp O(N^2*2^N). Đó chính là sử dụng quy hoạch động và bitmask (cách thường 
gọi là quy hoạch động trạng thái). 
Ý tưởng 
Để giải quyết bài toán này theo phương pháp quy hoạch động, các buớc thiết 
lập lời giải phải được lưu trữ để có thể tính toán từ các bài toán con. Rõ ràng ở đây, 
chúng ta phải lưu các đỉnh đã đi qua và đỉnh cuối cùng của một hành trình bất kỳ. 
Để làm việc này, ta dùng một mảng nhị phân N phần tử với ý nghĩa bit 1 tượng 
trưng cho các đỉnh đã được thăm và ngược lại. Từ đó, ta định nghĩa Fx [i,j] là chi 
phí tối ưu trong trạng thái i, j là đỉnh kết thúc hành trình (0 <= i <= 2^N -1; 1 <= j 
<= N). 
Ví dụ: 
Dãy [010011]2 tương đương trạng thái có 3 đỉnh được đi, và đỉnh kết thúc 
hành trình là đỉnh 5 (tính từ phải qua, bạn có thể lưu từ phải qua, vấn đề này không 
ảnh hưởng gì), với biểu diễn trong hệ thập phân tương ứng của dãy này là 19. Vậy 
hàm quy hoạch động của trạng thái này là Fx[19,5] 
Chi tiết thuật toán 
Với mỗi trạng thái I có j là đỉnh đến cuối cùng trong trạng thái này, xét mọi 
đỉnh k khác j mà k chưa được thăm trong trạng thái I. Gọi trạng thái mà hành trình 
của nó có chứa đỉnh k là X. 
Ví dụ: 
I = [010011] có các đỉnh 1,2,5 đã thăm. Giả sử k = 3 (thoả vì chưa đến được 
thành phố 3 trong trạng thái I), ta được trạng thái X = [010111]. 
Tóm lại, ở bước này: trạng thái X và trạng thái I chỉ khác nhau duy nhất ở 
đỉnh k. Dễ nhận thấy số thành phố đi được thấy đi được ở trạng thái X = số thành 
phố đi được ở trạng thái I + 1, suy ra việc tính toán Fx[X,k] sẽ dựa vào kết quả bài 
toán có kích thước nhỏ hơn nó là Fx[I,j] 
Tiếp theo, ta sẽ tối ưu Fx[X,k] theo công thức : Fx[X,k] = Min (Fx[X,k], 
Fx[I,j] + C[j,k]); 
Công thức trên sẽ lấy chi phí nhỏ hơn giữa trạng thái hiện tại (hành trình kết 
thúc tại k) và trạng thái hành trình kết thúc tại j cộng với chi phí di chuyển từ j -> 
k. 
Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học 
Trang 28 
Bước tìm đường đi có chi phí ngắn nhất chính là giá trị nhỏ nhất trong tất cả 
đường đi qua N đỉnh mà đường đi đó kết thúc tại thành phố i. Từ đó ta có kết quả 
bài toán là Min (Fx [2^N - 1, i]) với i =1..N. 
Số 2^N-1 thể hiện trạng thái mà N đỉnh đã được thăm. Ví dụ: 2^6 - 1 = 6310 
= 1111112 
Như đã đề cập ở trên, độ phức tạp cỡ khoảng 2^N*(N^2), dù sao cũng nhỏ 
hơn N! 
Bài toán 14: Chọn ô 
Cho một bảng hình chữ nhật kích thước 4×n ô vuông. Các dòng được 
đánh số từ 1 đến 4, từ trên xuống dưới, các cột được đánh số từ 1 đến n từ trái qua 
phải. Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j). Trên mỗi ô (i,j) có ghi 
một số nguyên aij , i =1, 2, 3, 4; j =1, 2, ..., n. Một cách chọn ô là việc xác định một 
tập con khác rỗng S của tập tất cả các ô của bảng sao cho không có hai ô nào trong 
S có chung cạnh. Các ô trong tập S được gọi là ô được chọn, tổng các số trong các 
ô được chọn được gọi là trọng lượng của cách chọn. 
Tìm cách chọn sao cho trọng lượng là lớn nhất. 
Ví dụ: Xét bảng với n=3 trong hình vẽ dưới đây: 
Cách chọn cần tìm là tập các ô S = {(3,1), (1,2), (4,2), (3,3)} với trọng 
lượng 32. 
Dữ liệu vào: Trong file văn bản SELECT.INP 
Dòng đầu tiên chứa số nguyên dương n là số cột của bảng. 
Cột thứ j trong số n cột tiếp theo chứa 4 số nguyên a1j, a2j, a3j, a4j, hai số 
liên tiếp cách nhau ít nhất một dấu cách, là 4 số trên cột j của bảng. 
Kết quả ra: Ra file văn bản SELECT.OUT 
Gồm 1 dòng duy nhất là trọng lượng của cách chọn tìm được. 
Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học 
Trang 29 
Ví dụ: 
SELECT.INP SELECT.OUT 
3 32 
-1 9 3 
-4 5 -6 
7 8 9 
9 7 2 
Hạn chế 
Trong tất cả các test: n ≤ 10000, |aij| ≤ 30000. Có 50% số lượng test với n ≤ 
1000. 
Tư tưởng chính: 
- Mỗi cột có 4 dòng nên ta có thể dùng dãy nhị phân gồm 4 bít để biểu diễn. 
Tùy vào giá trị của bít thứ k của cột thứ i bằng 0 hoặc1 cho biết dòng thứ k của cột 
thứ i có được chọn hay không. (0 ≤ k ≤ 3) 
- Dãy nhị phân có 4 bít ứng với 24 trạng thái, biểu diễn từ 0 tới 24-1. 
- Gọi F[i,x] là tổng trọng lượng lớn nhất xét từ cột thứ 1 tới cột thứ i và trạng 
thái chọn của cột thứ i được biểu diễn bằng biến x. 
- Ta có công thức quy hoạch động như sau: 
F[i,x]=max(F[i-1,y])+sum(i,x) 
Trong đó: 
- Biến x và y là hai trạng thái tương ứng của cột thứ i và i-1. Theo yêu cầu 
của bài toán thì trạng thái x và y phải thỏa mãn bít thứ k của biến x phải khác bít 
thứ k của biến y vì việc chọn ô phải thỏa mãn không có hai ô nào có chung 
cạnh.(Getbit(k,x)Getbit(k,y)) 
- Hàm Sum(i,x) là trọng số của cột thứ i tương ứng với trạng thái x. 
Cài đặt: 
Biến A chứa giá trị của bảng, biến m =24-1 với m+1 là số trạng thái 
Trong chương trình sử dụng một số hàm như sau: 
Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học 
Trang 30 
+) Lấy giá trị bít thứ k của trạng thái x: Getbit(k,x) 
Function Getbit(k,x:word):byte; 
Begin 
Getbit:=(x shr k)and 1; 
End; 
+) Hàm kiểm tra trạng thái x có thỏa mãn yêu cầu bài toán không (không có 
hai ô nào có chung cạnh), nghĩa là bít thứ k và bít thứ k-1của trạng thái x phải 
khác nhau: 
Function Ok(x:word):boolean; 
Begin 
Ok:=false; 
For k:=1 to 3 do 
If (getbit(k-1,x)=1)and(getbit(k,x)=1) then Exit; 
Ok:=true; 
End; 
+) Hàm kiểm tra trạng thái x và trạng thái y có thỏa mãn yêu cầu bài toán 
không (không có hai ô nào có chung cạnh), nghĩa là bít thứ k của trạng thái x và 
bít thứ k-1 của trạng thái y phải khác nhau: 
Function Check(x,y:word):boolean; 
Begin 
Check:=false; 
For k:=0 to 3 do 
If (getbit(k,x)=1)and(getbit(k,y)=1) then Exit; 
Check:=true; 
End; 
+) Tính trọng lượng của cột thứ i ứng với trạng thái x: 
Function sum(i,x:word):longint; 
Var T:longint; 
Begin 
T:=0; 
Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học 
Trang 31 
For k:=0 to 3 do 
If (getbit(k,x)=1) then T:= T+A[k+1,i]; 
Sum:=T; 
End; 
+) Thủ tục chính: 
Procedure process; Var max:longint; 
y,i:word; 
Begin 
For i:=1 to n do {Xét lần lượt n cột} 
For x:=0 to m do {Với mỗi cột i xét 24 trạng thái} 
If Ok(x) then {Nếu trạng thái x thỏa mãn bài toán} 
Begin 
max:=-vc; 
{Tìm trạng thái y của cột thứ i-1 có tổng trọng lượng lớn nhất} 
For y:=1 to m do 
If check(x,y)and(ok(y))then If 
max<F[i-1,y] then 
max:=F[i-1,y]; 
F[i,x]:=max+sum(i,x) 
End; 
End; 
+) Thủ tục in kết quả: 
Procedure printresult; 
Var Max:longint; 
 ff:text; 
Begin 
{Chú ý thêm trường hợp tất cả A[i,j]<0} 
{Tìm giá trị lớn nhất trong các trạng thái của cột thứ n} 
Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học 
Trang 32 
Max:=-vc; 
For x:=0 to m do 
If ok(x)and (max<F[n,x]) then Max:=F[n,x]; 
Assign(ff,fo); rewrite(ff); Writeln(ff,max); 
Close(ff); 
End; 
Nhận xét 
 Độ phức tạp thuật toán: O(24*24*N) đủ để giải quyết bài toán trên. 
Để giảm độ phức tạp của thuật toán ta có thể dùng 1 mảng B lưu những 
trạng thái thỏa mãn yêu cầu không có hai ô nào cùng cột có chung cạnh kết hợp 
với cấu trúc dữ liệu Foward Star để ứng với mỗi trạng thái x ta có danh sách các 
trạng thái y thỏa mãn. 
Bài toán 15: Chuyến du lịch - TRIP 
Trong kì nghỉ hè năm nay Sherry được bố thưởng cho 1 Tour du lịch quanh 
N đất nước tươi đẹp với nhiều thắng cảnh nổi tiếng (vì sherry rất ngoan). Tất nhiên 
sherry sẽ đi bằng máy bay. 
Giá vé máy bay từ đất nước i đến đất nước j là Cij (dĩ nhiên Cij có thể khác 
Cji ). Tuy được bố thưởng cho nhiều tiền để đi du lịch nhưng Sherry cũng muốn 
tìm cho mình 1 hành trình với chi phí rẻ nhất có thể để dành tiền mua quà về tặng 
mọi người (Các chuyến bay của Sherry đều được đảm bảo an toàn tuyệt đối). 
Bạn hãy giúp Sherry tìm 1 hành trình đi qua tất cả các nước, mỗi nước đúng 
1 lần sao cho chi phí là bé nhất. 
Dữ liệu vào: Trong file văn bản TRIP.INP 
Dòng 1: N (5 < N < 16) 
Dòng thứ i trong N dòng tiếp theo: Gồm N số nguyên, số thứ j là Cij (0 < Cij 
< 10001) 
Kết quả ra: Ra file văn bản TRIP.OUT 
Gồm 1 dòng duy nhất ghi chi phí bé nhất tìm được 
Ví dụ 
TRIP.INP TRIP.OUT 
Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học 
Trang 33 
6 8 
0 1 2 1 3 4 
5 0 3 2 3 4 
4 1 0 2 1 2 
4 2 5 0 4 3 
2 5 3 5 0 2 
5 4 3 3 1 0 
Hướng dẫn: 
- Ta nhận thấy đây là bài toán tìm đường đi Hamilton, một bài toán khá quen 
thuộc: cho N đỉnh, tìm đường đi sao cho mỗi đỉnh được thăm duy nhất một lần, và 
chi phí thăm N đỉnh là thấp nhất. 
- Với dạng toán này, thông thường nếu N nhỏ (≤10), ta có thể giải quyết bài 
toán bằng phương pháp nhánh cận. Nhưng nếu giới hạn N tăng lên đến 20, thì việc 
sử dụng phương pháp nhánh cận để giải quyết sẽ không còn khả thi nữa. Trong 
trường hợp này, ta có cách tiếp cận khác để giải quyết bài toán một cách tối ưu 
hơn, với độ phức tạp O(N2*2N). 
- Dãy nhị phân có N bít ứng với 2n trạng thái, biểu diễn từ 0 tới 2n-1 cho biết 
các đỉnh đã được thăm hay chưa. 
- Gọi F[i,x] là tổng chi phí nếu sherry đang ở Đất nước i và trạng thái các 
nước đã đi qua được lưu vào biến. 
- Công thức Quy hoạch động: 
F[i,x] = min( F[j,y] + C[j,i] ) 
Trong Đó 
- j là đất nước đã được đánh dấu đi qua trong x. 
- y là trạng thái giống như trạng thái x nhưng đất nước i chưa được đánh dấu. 
Bài toán 16: Cô gái chăn bò - COWGIRL 
Trên một thảo nguyên nhỏ bé có 1 gia đình gồm 3 anh em: 2 người anh trai 
là Nvutri và Andorea còn người em gái là Lola. Cuộc sống gia đình khá giả nhưng 
Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học 
Trang 34 
gia đình có truyền thống chăn nuôi và muốn để các con tự lập nên cha mẹ 3 người 
quyết định để các con hằng ngày sẽ đi chăn 1 số bò nào đó (tùy ý 3 người con). 
Thảo nguyên là 1 cánh đồng chia làm M*N ô vuông, mỗi con bò chỉ đứng 
trong 1 ô và mỗi ô chỉ chứa 1 con bò.Chỉ có 1 quy tắc duy nhất là không bao giờ 
được để 4 con bò tạo thành 1 hình vuông 2*2 hoặc để trống 1 khu đất 2*2. 
Hai người anh mải chơi nên đã hối lộ kem để Lola chăn bò 1 mình. Lola 
muốn biết tất cả có bao nhiêu cách xếp bò thỏa mãn quy tắc trên để đề phòng mọi 
trường hợp. Vì con số này rất lớn nên hãy giúp Lola tính toán con số này. 
Dữ liệu vào: Trong file văn bản COWGIRL.INP 
Dòng đầu gồm 1 số T duy nhất là số test (T ≤ 111) 
T dòng tiếp theo gồm 2 số M, N cho biết kích thước của thảo nguyên (M*N 
≤ 30) 
Kết quả ra: Ra file văn bản COWGIRL.OUT 
Gồm T dòng, mỗi dòng ứng với 1 test là số cách xếp bò của test đó. 
Ví dụ: 
COWGIRL.INP COWGIRL.OUT 
1 1 
1 
2 
Hướng dẫn: 
- Ta thấy M*N<=30 nên tồn tại một số M hay N không lớn hơn 5. 
- Giả sử là M là số dòng không quá 5. Ta có thể sử dụng số có không quá 5 
bit nhị phân Để mô tả trạng thái chọn ở mỗi cột. 
- Gọi F[i,x] là số cách xếp bò thỏa mãn yêu cầu bài toán xét từ cột thứ 1 tới 
cột thứ i và trạng thái chọn của cột thứ i được biểu diễn bằng biến x.. 
- Công thức Quy hoạch động: 
F[i,x] = F[i,x] + F[i-1,y] ) 
Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học 
Trang 35 
C. KẾT LUẬN 
Đề tài này mang tính chất thời sự và cấp thiết trong việc trang bị cho các em 
học sinh giỏi tin học về cách tìm thuật toán cho bài toán là một điều hết sức cần 
thiết. 
Các giáo viên bồi dưỡng học sinh giỏi cần tìm, và thu thập các thuật toán 
giải các bài toán theo dạng từ dễ đến khó là phương pháp dạy lập trình đặc biệt có 
hiệu quả. Chính vì thế truyền đạt cho các em kiến thức để các em tiếp cận được các 
thuật toán là một điều không thể thiếu đối với các giáo viên và các em được bồi 
dưỡng thi học sinh giỏi. 
Vì khuôn khổ bài viết, vì vốn kiến thức còn hạn hẹp, tôi rất mong nhận được 
các ý kiến trao đổi, góp ý của đồng nghiệp. 
Tôi xin chân thành cảm ơn . 
Hưng Nguyên, ngày 03/03/2021 
 TÁC GIẢ 
 Phan Văn Thế