[Học thêm HSG9] Quy hoạch động

Cho một dãy số nguyên gồm N phần tử \(A_1, A_2, ... , A_N\).
Biết rắng dãy con tăng đơn điệu là 1 dãy \(A_i,,..., A_j\) thỏa mãn \(i_1 < i_2 <.. <i_k\) và \(A_i, < A_{i+1} < .. < A_j\). Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử?

Inpt

• Dòng 1 gồm 1 số nguyên là số \(N\) (\(1 ≤ N ≤ 1000\)).
• Dòng thứ 2 ghi N số nguyên \(A_1, A_2, ..., A_n\) (\(|A_i| ≤ 10^9\)).

Output

Ghi ra độ dài của dãy con tăng đơn điệu dài nhất.

6
1 2 5 4 6 2

4

Cứ vào mùa hè hằng năm, trường \(NKT\) sẽ tổ chức một buổi giao lưu ngoại khóa giữa các trường trong thành phố, và các trò chơi đồng đội là thứ không thể nào thiếu. Có \(n\) học sinh đến từ \(m\) trường khác nhau sẽ tham gia các trò chơi năm nay. Các học sinh sẽ đứng xếp hàng theo thứ tự đánh số từ \(1\) tới \(n\). Ban tổ chức dự định sẽ chia các học sinh thành một số đội từ \(n\) học sinh, mỗi học sinh thuộc đúng duy nhất một đội và một đội phải có tối thiểu một học sinh.

Để cho đơn giản, họ sẽ tách hàng đang đứng hiện tại thành một hoặc một số hàng liên tiếp và mỗi hàng sau khi tách như thế sẽ là một đội. Tuy nhiên, một đội không thể có học sinh thuộc quá nhiều trường khác nhau, bởi như thế thì các thầy cô sẽ rất khó quản lý. Mặt khác, một đội cũng không thể có học sinh thuộc quá ít trường khác nhau, bởi khi đó thì các bạn sẽ chỉ chơi với những người cùng trường, gây chia rẽ nội bộ và gây khó khăn cho các học sinh trong việc làm quen với những bạn mới trong đội mình. Sau khi cân nhắc kỹ càng, ban tổ chức quyết định một đội sẽ có các thành viên thuộc tối thiểu \(l\) trường khác nhau và tối đa \(r\) trường khác nhau.

Tuy ràng buộc phức tạp như vậy, nhưng vẫn có rất nhiều cách khác nhau để xếp đội, vì vậy bạn hãy giúp ban tổ chức tính số cách xếp đội khác nhau nhé. Lưu ý là có thể xếp thành một đội duy nhất gồm cả \(n\) thí sinh.

Input

• Dòng đầu tiên chứa các số nguyên \(n,m,l,r(1 \leq m \leq n \leq 10^3)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n(1 \leq a_i \leq m)\) với \(a_i\) là trường của học sinh thứ \(i\).

Output

Một dòng duy nhất chứa số cách xếp đổi. Kết quả chia lấy dư cho \(19122007\)

Subtask

• Subtask \(1(30\%)\): \(n \leq 10\).
• Subtask \(2(20\%)\): \(n \leq 100\).
• Subtask \(3(50\%)\): \(n \leq 10^3\).

6 6 1 1
1 2 3 4 5 6

1

6 6 6 6
1 2 3 4 5 6

1

9 4 2 3
1 2 4 3 2 2 1 3 4

6

Xâu ký tự \(X\) được gọi là xâu con của xâu ký tự \(Y\) nếu ta có thể xoá đi một số ký tự trong xâu \(Y\) để được xâu \(X\).
Cho biết hai xâu ký tự \(A\) và \(B\), hãy tìm xâu ký tự \(C\) có độ dài lớn nhất và là con của cả \(A\) và \(B\).

Input

• Dòng 1: chứa xâu \(A\) (\(|A| <= 2000\)).
• Dòng 2: chứa xâu \(B\) (\(|B| <= 2000\)).

Output

• Chỉ gồm một dòng ghi độ dài xâu \(C\) tìm được

abc1def2ghi3
abcdefghi123

 10

Trong siêu thị có \(N \leq 1000\) đồ vật, đồ vật thứ \(i\) có khối lượng \(W_i \leq 1000\), giá trị \(V_i \leq 10^9\)
Có một tên trộm đột nhập vào siêu thị và mang theo một cái túi có thể chứa được mọi đồ vật sao cho tổng khối lượng các món đồ không vượt quá \(M(M \leq 1000)\)

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\).
• \(N\) dòng tiếp theo, mỗi dòng chứa khối lượng \(W_i\) và giá trị \(V_i\) của món quà thứ \(i\).

Output

Ghi giá trị lớn nhất tên trộm có thể lấy.

5 15
12 4
2 2
1 1
1 2
4 10

15

Cho bảng \(A\) kính thước \(m*n\)(\(m\) dòng, \(n\) cột), trên đó ghi các số nguyên dương \(a_{ij}\). Một người xuất phát tại ô nào đó của cột \(1\), cần cang cột \(n\)(tại ô nào cũng được).
Quy tắc đi: Từ ô \((i,j)\) chỉ được quyền sang một trong \(3\) ô \((i,j+1)\);\((i-1,j+1)\);\((i+1,j+1)\).
Hãy tìm một đường đi sao cho tổng tất cả các số trên đường đi đó là lớn nhất.

Dữ liệu vào

• Dòng đầu ghi hai số nguyên dương \(m\),\(n\) là số hàng và số cột của bảng.
• \(m\) dòng tiếp theo, dòng thứ \(i\) ghi \(n\) số trên hàng \(i\) của bảng theo thứ tự từ trái qua phải.

Dữ liệu ra

Gồm một dòng duy nhất ghi tổng lớn nhất tìm được.

Giới hạn

• \(1 \leq n,m,|a_{ij}| \leq 100\)

5 7
9 -2 6 2 1 3 4
0 -1 6 7 1 3 3
8 -2 8 2 5 3 2
1 -1 6 2 1 6 1
7 -2 6 2 1 3 7

41

Cho một dãy số nguyên gồm N phần tử \(A_1, A_2, ... , A_N\).
Biết rắng dãy con giảm đơn điệu là 1 dãy \(A_i,,..., A_j\) thỏa mãn \(i_1 < i_2 <.. <i_k\) và \(A_i > A_{i+1} > .. > A_j\). Hãy cho biết dãy con giảm đơn điệu dài nhất của dãy này có bao nhiêu phần tử?

Inpt

• Dòng 1 gồm 1 số nguyên là số \(N\) (\(1 ≤ N ≤ 1000\)).
• Dòng thứ 2 ghi N số nguyên \(A_1, A_2, ..., A_n\) (\(|A_i| ≤ 10^9\)).

Output

Ghi ra độ dài của dãy con giảm đơn điệu dài nhất.

6
1 2 5 4 6 2

3

Alice vừa đạt giải quán quân trong một kỳ thi lập trình danh giá. Ban tổ chức trao thưởng thông qua một trò chơi như sau. Có \(n\) thẻ xếp trên một hàng dài, trên mỗi thẻ viết một số nguyên dương. Ban tổ chức cho phép Alice thực hiện nhiều bước để chọn ra đúng \(k\) cặp thẻ, mỗi bước thực hiện theo một trong các quy tắc sau:
\(1\). Chọn \(2\) thẻ ở đầu hàng.
\(2\). Chọn \(2\) thẻ ở cuối hàng.
\(3\). Chọn \(1\) thẻ ở đầu hàng và \(1\) thẻ cuối hàng.
\(4\). Loại \(1\) thẻ đầu hàng ra khỏi hàng.
\(5\). Loại \(1\) thẻ cuối hàng ra khỏi hàng.
Sau mỗi bước nếu chọn được \(2\) thẻ thì loại \(2\) thẻ đó ra khỏi hàng và Alice nhận được số tiền thưởng bằng giá trị tuyệt đối của hiệu hai số ghi trên thẻ đó.

Yêu cầu

Hãy giúp Alice tìm cách chơi chọn đúng \(k\) cặp thẻ để đạt được tổng số tiền thưởng là lớn nhất.

Dữ liệu vào

• Dòng thứ nhất chứa hai số nguyên dương \(n\) và \(k\) \((2*k \leq n);\)
• Dòng thứ hai chứa \(n\) số nguyên dương là giá trị ghi trên từng thẻ, mỗi thẻ một số tương ứng lần lượt từ đầu hàng. Các số có giá trị không vượt quá \(10^9\)

Các số trên cùng một dòng cách nhau bởi dấu cách.

Giới hạn

• Có \(40\%\) số test ứng với \(40\%\) số điểm bài thỏa mãn điều kiện \(n \leq 300, k \leq 2;\)
• \(40\%\) số test khác ứng với \(40\%\) số điểm của bài thỏa mãn điều kiện \(n \leq 30,2*k =n\);
• \(20\%\) số test còn lại ứng với \(20\%\) số điểm của bài thỏa mãn điều kiện \(n \leq 300;\)

6 2
1 3 10 2 1 4

12

Có \(N\) người sắp hàng mua vé dự buổi hoà nhạc. Ta đánh số họ từ \(1\) đến \(N\) theo thứ tự đứng trong hàng. Mỗi người cần mua một vé, song người bán vé được phép bán cho mỗi người tối đa hai vé. Vì thế, một số người có thể rời hàng và nhờ người đứng trước mình mua hộ vé. Biết \(t_i\) là thời gian cần thiết để người \(i\) mua xong vé cho mình. Nếu người \(i+1\) rời khỏi hàng và nhờ người \(i\) mua hộ vé thì thời gian để người thứ \(i\) mua được vé cho cả hai người là \(r_i\) (tất nhiên người đầu hàng sẽ không thể nhờ ai mua vé hộ).

Hãy tính xem, nếu mọi người nhờ mua vé một cách thích hợp nhất có thể thì tổng thời gian người bán hàng phải phục vụ ít nhất là bào nhiêu?

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương \(N (1<N \leq 60000)\)
• Dòng thứ hai ghi \(N\) số nguyên dương \(t_1,t_2,...,t_N(1 \leq t_i \leq 30000.\)
• Dòng thứ ba ghi \(N\) số nguyên dương \(r_1,r_2,...,r_N(1 \leq r_i \leq 30000.\)

Dữ liệu ra

In ra tổng thời gian phục vụ nhỏ nhất.

5
2 5 7 8 4
4 9 10 10

18

4
5 7 8 4
50 50 50

24