ao bèo của cụ Nguyễn Khuyến

[thuonghcm]

Ao bèo (loại bèo cám) của cụ Nguyễn Khuyến có nuôi cá Rô.
Cái ao có dt m x n (VD: m=8,n=7 mà điều đặc biệt là cá ham ăn bèo hơn ăn câu). Cụ giận quá không thèm câu nữa mà đi tính diện tích phần bèo hình vuông (max) không bị (ăn) bởi mấy con cá rô.
VD : bèo là 1, cá rô ăn "bèo" hay ăn móng làm bèo tan là 0
1 0 1 1 1 1 1
1 1 1 1 1 0 1
1 1 1 1 0 1 1
1 1 1 1 1 1 1
0 1 1 1 1 0 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1

Theo VD trên thì cụ lấy cây cần câu ghi trên bờ ao là ếch bằng mười sáu
cụ thở phào,
rít miếng thuốc lào,
miệng nói úi chào,
thiệt là ....tào lao.
heheheheheheheh

[tastsuka]

xay dựng f[n][m]
st[i]=0; c[i]=0;
for j=1->m
for i=1->n
if a[i][j]=0
st[i]++ f[i][st[i]]=j;


for i=1->n
for j=1->m
ì (a[i][j]!=0)
xet(i,j)

->xet(i,j)
{
k=min(n-i, m-j)
for (u=k->0)
if (k^2>dt)
if ok(i,j,k)
{ dt=(k^2; }
}

-> boolean ok(i,j,k)
{
for t=j->j+k
for u=c[i]->st[i]
{
if (f[i][u]<j c[i]++)
if (f[i][u]<j+k {ok=false exit}
}
ok=true;

}


cơ bản là thế, có thể sai xót chút xíu bà con thông cảm

[truongngocdai]

ko hỉu bài này có yêu cầu gì

[tastsuka]

Yêu cầu tìm ô vuông có S max chỉ chứa 1 trong matran [0,1] thôi mà
Có thể phát triển tìm S hình chữ nhật max hoặc S chữ T max

[thuonghcm]

cơ bản là thế, có thể sai xót chút xíu bà con thông cảm

nên sửa lại là:
nâng cao là vậy, chắc chắn sai sót "rất nhiều" bà con cứ cảm

[truongngocdai]

theo mình thì bài này ko khó lắm, mình làm = duyệt

[thuonghcm]

vậy sao TND không duyệt thử coi!?!!?!

[truongngocdai]

uh, duyệt được mà dùng DFS hay BFS cũng được, để mai mình post lời giải

[bete]

Tui xin ké 1 chút: nếu mình thích mày mò về thuật toán thì chỉ nên xài phương pháp duyệt như là phương cách cuối cùng:

- về mặt ý tưởng thì duyệt hầu như lúc nào cũng ra
- về mặt khả thi thì duyệt hầu như là chậm (độ phức tạp là lớn)
- nếu mình cứ nghĩ tới duyệt hoài, lâu ngày thành thói quen => ít khi nghĩ tới cách khác

Về bài toán, tui xin thay đổi đề bài 1 chút rồi sẽ đổi ngược trở lại sau: ao là hình vuông; và mình muốn tìm hình chữ nhựt lớn nhứt

Tui xin thử làm rắc rối 1 chút nhưng hy vọng độ phức tạp là O(N^2):

Giả sử mình đang ở ô [i,i]. Mình viết 1 thủ tục P sao cho khi gọi P(i,i) thì trả về:
- diện tích hình chữ nhựt con nhỏ nhứt chứa trong hình vuông con (i,i,N,N)
- 1 danh sách (vị trí và kích thước) các hình chữ nhựt con có biên là mép trên của hình vuông con (i,i,N,N) đang xét
- 1 danh sách (vị trí và kích thước) các hình chữ nhựt con có biên là mép trái của hình vuông con (i,i,N,N) đang xét
- kích thước của hình chữ nhựt con có biên là mép trên và mép trái của hình vuông con (i,i,N,N) đang xét
Ví dụ:

AAAAAoooBBBBBBoo
AAAAAoooBBBBBBoo
AAAAAooooooooooo
oooooDDDDDDDoooo
CCCooDDDDDDDoooo
CCCooDDDDDDDoooo
CCCooDDDDDDDoooo
CCCooooooooooooo
oooooooEEEEooooo

=> trả về:
- diện tích hình chữ nhựt con lớn nhứt D
- danh sách (vị trí và kích thước) các hình chữ nhựt con B
- danh sách (vị trí và kích thước) các hình chữ nhựt con C
- kích thước hình chữ nhựt con A

Bây giờ mình đi lùi lại 1 bước => đứng ở ô [i-1, i-1]
Mình sẽ gọi P(i,i):
- các hình chữ nhựt con loại B có thể tăng chiều cao nhờ trộn với với các ô ở dòng (i-1)
- các hình chữ nhựt con loại C có thể tăng chiều rộng nhờ trộn với các ô ở cột (i-1)
- hình chữ nhựt con loại A có thể tăng thêm chiều cao và/hoặc chiều rộng nhờ trộn với các ô ở dòng (i-1) và cột (i-1)

11111ooooo1o11ooo
1AAAAAoooBBBBBBoo
1AAAAAoooBBBBBBoo
1AAAAAooooooooooo
ooooooDDDDDDDoooo
1CCCooDDDDDDDoooo
1CCCooDDDDDDDoooo
1CCCooDDDDDDDoooo
1CCCooooooooooooo
ooooooooEEEEooooo

Như vậy mình:
- cập nhựt danh sách (vị trí và kích thước) các hình chữ nhựt con loại B: O(N)
- cập nhựt danh sách (vị trí và kích thước) các hình chữ nhựt con loại C: O(N)
- cập nhựt kích thước hình chữ nhựt con loại A: O(N)
- cập nhựt diện tích hình chữ nhựt con lớn nhứt chứa trong hình vuông con (i-1, i-1, N, N) đang xét: O(N)

=> chính là các giá trị trả về cho P(i-1, i-1)

Từ ý tưởng đệ qui ở trên => mình xài quy hoạch động

Sau cùng mình sửa lại 1 chút để xài với đề bài gốc: ao hình chữ nhựt và cần tìm diện tích hình vuông con lớn nhứt
=> độ phức tạp là O(M x N)

(có gì sai sót mong được góp ý, xin cám ơn)

-thân

[truongngocdai]

hình như mình thấy 1 lần báo THNT đã đăng và giải bài này rồi, hình như là gọi chiều cao ... gì gì đó