Mảng nhiều chiều (tiếp)

1. Chữa bài về nhà

Tính tổng ma trận vuông k*k lớn nhất với độ phức tạp thuật toán O(m*n*k*k).

Gợi ý:

1. Tính tổng 1 ô vuông k*k để làm giá trị max.

2. Dùng vòng lặp for tính tổng những ô vuông còn lại, lưu vào 1 ma trận có kích thước (m – k + 1)*( n – k + 1), so sánh với giá trị max để tìm được tổng lớn nhất.

Code:

input.txt

2. Bài tập

Cho 1 ma trận A(m*n), xây dựng ma trận B(m*n) với:

B[x][y] = Sum(a[i][j]) với i chạy từ 0 đến x, j chạy từ 0 đến y.

Code:

3. Bài tập về nhà

Dựa vào bài tập 2, viết chương trình tìm tổng lớn nhất của ô vuông có kích thước k*k với độ phức tạp thuật toán O(m*n)

Bài làm thêm:

Cho 1 khúc gỗ được chia thành n đoạn bằng nhau, tại những điểm chia trên khúc gỗ có k con kiến đang bò về 2 hướng khác nhau (bò về 2 phía đầu mút), tất cả đều bò với vận tốc như nhau (ví dụ 1mm/s). Biết rằng cứ 2 con kiến bò ngược chiều nhau nếu gặp nhau thì sẽ quay đầu ngược lại hướng đang chuyển động, hỏi sau bao lâu thì các con kiến bò hết ra khỏi cành cây (không còn con nào trên cành cây)?

Ảnh minh họa, nguồn Internet

FILE input.txt: input.txt

4. Tài liệu tham khảo

Một số bài toán quy hoạch động điển hình – VNOI.

http://vnoi.info/wiki/algo/dp/basic-problems

 

The following two tabs change content below.