Xin cách suy nghĩ và giải bài tập bằng phương pháp quy hoạch động

Việc xét hiệu trên và dưới của domino tương dương việc đặt dấu (+,-) cho hiệu trên dưới của 1 domino. Nó tương dương với việc xếp thành hai nhóm (dấu +) và (dấu -) sao cho hiệu trị tuyệt đối nhỏ nhất.
Việc xét tìm giá trị đó thì chỉ việc sinh ra tất cả giá trị của nó bằng cách duyệt mảng
F[1…n][-n6…n6] như sau

for i =0->n:
For j=-6n ->6n:
    if F[i-1][j]:
       F[i][j+a[i]-b[i]]=True
       F[i][j-a[i]+b[i]]=True

việc duyệt mảng f sao cho có trị tuyệt đối nhỏ nhất là kết quả
Việc truy vết thì bạn tự nghĩ

Qui hoạch động lấy tư tưởng chia để trị với 1 bài toán thường thì mình sẽ đi từ kết quả để tìm ra cách chia nhỏ bài toán ví dụ bài trên giả sử đã xếp đc cấu hình tối ưu từ 1 -> n-1 thì cấu hình thứ n cần xếp ntn
TH1: ko lật ô thứ n
Th2: lật ô thứ n
Xét 2 TH này là bao quát tất cả các trường hợp xẩy ra.
Từ đó để biết được xem đến con thứ n thì nên lật hay không thì điều cần là các con phía trước đã xếp đc tổng là bao nhiêu => Khởi đầu: F[i,s] là giá trị để nhận biết xem dùng đến con thứ i có tạo ra tổng s hay ko.F[i,s]= F[i-1,s-(a[i] ± b[i])] từ đây đủ để tìm ra yêu cầu là tổng bé nhất rồi :))
Đọc lại bài toán thấy còn yêu cầu ít nhất, nhận thấy cái hàm F[i,s] còn dư dả quá :v ép cho nó thành tạo thành tổng s đến con thứ i lật ít nhất thì sao :v

Em cám ơn
Vậy với những trường hợp phân thành (+),(-) như bài này có thể dùng phương pháp này phải không

Em đang học cách suy nghĩ, chỉ cần hướng thôi ạ. Kiểu nhìn nhận thấy điều A thì ta suy được mình phải làm gì với kiểu như thế. Bài kia em xong rồi cám ơn anh AI_Android và Gió.
Trang không cho chèn ảnh, trình bày khó quá

Cho một bảng số A gồm M dòng, N cột, các giá trị của bảng A chỉ là 0
hoặc 1. Ta muốn cắt bảng A thành các hình chữ nhật con sao cho các hình
chữ nhật con có giá trị toàn bằng 1 hay toàn bằng 0. Một lần cắt là một nhát
cắt thẳng theo dòng hoặc theo cột của một hình chữ nhật thành hai hình chữ
nhật riêng biệt. Cứ tiếp tục cắt cho ñến khi hình chữ nhật toàn bằng 1 hay
toàn bằng 0. Hãy tìm cách cắt ñể ñược ít hình chữ nhật nhất mà các hình chữ
nhật con có giá trị toàn bằng 1 hay toàn bằng 0.
Ví dụ: Bảng số 5×5 sau ñược chia thành 8 hình chữ nhật con.
0 1 0 0 1
0 1 0 0 1
1 1 0 0 1
1 1 1 0 0
0 0 1 0 0

0  | 1 | 0   0 | 1

0  | 1 | 0   0 | 1
--------
1    1 | 0   0 | 1
       -----------
1    1 | 1 | 0   0
--------
0   0  | 1 | 0   0

Dữ liệu vào trong file HCN2.INP

• Dòng ñầu là 2 số nguyên dương M, N (M,N≤30)
• M dòng tiếp theo, mỗi dòng N số chỉ gồm 0 hoặc 1 thể hiện bảng số A
  Kết quả ra file HCN2
  Gồm 1 dòng duy nhất chứa một số duy nhất là số hình chữ nhật ít nhất

Trang không cho chèn ảnh

Rê ảnh thả vào phần Reply, ảnh sẽ tự động được tải lên (nhớ đợi cho ảnh upload xong nhé), áp dụng cho cả việc tạo topic mới luôn

Cái này giờ mới biết, chẳng thấy topic nào có ảnh tưởng không có chức năng. Hóa ra dùng HTML

Ai giúp với, nhân tiện cho mail hay địa chỉ gì để liên lạc nhờ chỉ giáo dùm

F[a,b,c,d] là hình số hình chữ nhật ít nhất trong hình nhật có đỉnh trái trên là a,b chiều dài,rộng là c,d
init:
1: if S[a,b,c,d] =cd hoac bang 0 //cac phan tu trong hinh chu nhat dang xet la giong nhau
thi F[a,b,c,d]=1; elseF[a,b,c,d]=cd;
F[a,b,c,d]= min ( F[a,b,c,k]+F[a,b+k,c,d-k], F[a,b,t,d]+ F[a+t,b,c-t,d] )

O(n^2m^2(n+m))