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.

Trả lời dohonghuan
  Hiện bài gốc

Bạn phải mô tả cụ thể thuật toán thì mọi người mới giúp bạn được. 

Trả lời khanhptnk
  Hiện bài gố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];
 

Trả lời dohonghuan
  Hiện bài gốc

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

 

Trả lời RR
  Hiện bài gốc

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 

Trả lời TV_TN
  Hiện bài gốc
<p>mình lật ngược đồ thị lại rồi làm y chang cái đồ thị ban đầu rồi lấy min 2 kết quả :D</p>
Trả lời dohonghuan
  Hiện bài gốc

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.

Trả lời ladpro98
  Hiện bài gốc

Vậy thuật toán của bài này là sao a ?

Trả lời dohonghuan
  Hiện bài gốc

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 .