BÀY TRANH CHO N BỨC TRANH MÃ SỐ TỪ 1..N (N≤50). NGƯỜI TA CẦN C...

Bài 3 - Bày tranh Cho n bức tranh mã số từ 1..n (n≤50). Người ta cần chọn ra một bức để đặt ở cửa phịng tranh, số cịn lại

được treo thẳng hàng trong phịng trên m vị trí định sẵn cĩ mã số 1..m từ trái qua phải. Các bức tranh phải được treo theo trật

tự nghiêm ngặt sau đây: tranh cĩ số hiệu nhỏ phải treo ở trên tranh cĩ số hiệu lớn.

Biết các thơng tin sau về mỗi bức tranh:

- Tranh thứ i treo tại cửa sẽ đạt trị thẩm mỹ c[i];

- Tranh thứ i treo tại vị trí j sẽ đạt trị thẩm mỹ v[i,j].

- m+1≥n.

- Các giá trị thẩm mỹ là những số tự nhiên khơng vượt quá 50.

Yêu cầu: Hãy xác định một phương án treo tranh để cĩ tổng trị thẩm mỹ là lớn nhất.

Dữ liệu: Picture.INP

- Dịng thứ nhất ghi n, m (cách nhau 1 dấu cách)

- Dịng tiếp theo là n giá trị c.

- Tiếp đến là n dịng, dịng i gồm m vị trí v[i,1], v[i,2],..v[i,m].

Kết quả: Picture.OUT

- Dịng thứ nhất ghi giá trị thẩm mỹ lớn nhất tìm được

- Dịng thứ hai: ghi mã số hiệu bức tranh treo ở cửa phịng tranh.

- Dịng thứ 3 ghi n-1 số tự nhiên sắp tăng chặt cho biết mã số các vị trí được chọn để treo tranh

Ví dụ:

Tư tưởng thuật tốn: Bài 1 - Dãy con lồi Phân tích bài tốn: Theo định nghĩa của đề bài: "Dãy giá trị nguyên A =(A

, A

,

A

,.., A

) được gọi là lồi, nếu nĩ giảm dần từ A

đến một A

nào đĩ, rồi tăng dần tới A

" ta thấy rằng phần tử đặc biệt trong

một dãy lồi là điểm gãy A

, dãy đơn điệu tăng về hai phía của điểm gãy. Do khơng được định nghĩa rõ nên ở đây chúng ta tự

ngầm định: 1<i< N (nếu trùng với 1 hoặc N thì dãy trở thành đơn điệu tăng hoặc giảm.

Từ nhận xét trên, ta giải quyết bài tốn như sau:

- Xây dựng mảng U thoả mãn: U[i] số phần tử của dãy giảm dài nhất là dãy con của dãy X

, X

, .. , X

, với X

là phần tử nhỏ nhất của dãy con.

- Xây dựng mảng D thoả mãn: D[i] số phần tử của dãy tăng dài nhất là dãy con của dãy X

, X

, .., X

, với X

- Điểm gãy được chọn là điểm vt thoả mãn:

(D[i]>1 và D[j]>1 để đảm bảo điểm gãy khơng nằm ở đầu mút)

Độ dài của dãy lồi dài nhất là: U[vt]+D[vt]-1.

Lưu ý: Do đề bài nên một số bài cho kết quả là những dãy đơn điệu, cịn một số trả lời là khơng cĩ dãy lồi, cả hai kết

quả trên đều được chấp nhận. Bài giải sẽ cho kết quả là 0 với những dãy chỉ cĩ điểm gãy trùng với một trong hai điểm đầu

mút.