Mọi người cho em hỏi câu này với:
Các chiều của hình chữ nhật con mà ta chọn có thể bằng 1 được không? Tức là hình chữ nhật con có thể có kích thước 1*a hay a*1 được không? (a>=1)
Mọi người cho em hỏi câu này với:
Các chiều của hình chữ nhật con mà ta chọn có thể bằng 1 được không? Tức là hình chữ nhật con có thể có kích thước 1*a hay a*1 được không? (a>=1)
Có thể nhé :D
Thế bị 75 đ là do lỗi gì vậy ? Mình cũng 75 chưa lên 100.
Bạn phải mô tả cụ thể thuật toán thì mọi người mới giúp bạn được.
Với mọi vị trí i, j em tìm độ cao tại đó:
for j:=1 to n do
if a[i, j]>=a[i-1, j] then
inc(h[j])
else h[j] :=1;
Sau đó e dùng Stack để tìm left với right sau cho độ cao h tại điểm đó là nhỏ nhất trong L với R.
Bởi vì để nói :các số trên 1 hàng bất kỳ tính từ trái sang phải có độ cao không giảm nên e tiếp tục tìm Left và Right cho dòng i
for j:=1 to n do
if a[i, j]>=a[i, j-1] then ls[j] :=ls[j-1]
else ls[j] := j;
rs[n+1] :=n;
for j:=n downto 1 do
if a[i, j+1]>=a[i, j] then rs[j] :=rs[j+1]
else rs[j] :=j;
Cuối cùng e đặt y := max(Left của h[j], Left của dòng j); x:= min(Right của h[j], Right của dòng j)
kết quả là (x-y+1)*h[j];
Em thử test này nhé:
4 9
10 11 12 13 9 8 7 6 5
14 15 16 17 4 3 2 1 0
18 19 20 21 22 23 24 25 26
27 28 29 30 31 32 33 34 35
Em cũng 75đ. Thuật giống bạn #dohonghuan . Nhưng vẫn chưa biết phải giải quyết trường hợp đó thế nào ạ?
Không đảm bảo được hình chữ nhật có các dòng thỏa đề bài (trừ dòng cuối cùng ). Mọi người giải đáp giúp em chỗ này
Làm như vậy thì sai test này:
3 6
1 1 0 1 2 3
2 1 0 1 1 4
3 4 0 0 0 0
Đáp án đúng là 4.
Vậy thuật toán của bài này là sao a ?
Bài này cần biến đổi input sao cho giống bài QBRECT.
Bản chất 2 bài là chưa giống nhau. Ở bài này, nếu ta có h[i,j]>=h[i-1,j] và h[i,j+1]>=h[i-1,j+1] thì vẫn chưa chắc chắn sẽ tạo được một HCN 2x2 thỏa đề, trong khi đó ở bài QBRECT chỉ cần a[i,j]=a[i-1,j] và a[i,j+1]=a[i-1,j+1] đã có thể tạo thành HCN 2x2 .