DP lis

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_1],... A[i_k]\) thỏa mãn
\(i_1 < i_2 < ... < i_k\) và \(A[i_1] < A[i_2] < .. < A[i_k]\).

Yêu cầu:

• 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ử.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương \(N\) (\(1 ≤ N ≤ 1000\))
• Dòng thứ 2 ghi N số nguyên \(A[1], A[2], .. A[N] (1 ≤ A[i] ≤ 1000000)\).

Kết quả

• 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

Nguồn: vn.spoj

Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên dương \(A_1, A_2, ..., A_N\). Dãy \(C\) được gọi là dãy con tăng độ dài \(K\) của \(A\) nếu thoả mãn các điều kiện sau:

• \(K \geq 1\).
• \(1 \leq i_1 < i_2 < i_3 < ... < i_K \leq N\).
• \(C_1 = A_{i_1}, C_2 = A_{i_2}, ..., C_K = A_{i_K}\).
• \(C_1 < C_2 < ... < C_K\) nếu \(K \geq 2\)

Yêu cầu: Gọi \(SumC = \sum\limits_{i=1}^K C_i\). Tìm \(SumC\) lớn nhất có thể của dãy \(C\).

Input

• Dòng thứ nhất gồm số nguyên dương \(N\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, A_3, ..., A_N\).

Output

• In ra một số nguyên dương duy nhất là kết quả bài toán.

Constraints

• \(N\leq 10^5\)
• \(A_i\leq 10^9\)

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N\leq 10^3\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
1 2 3 5 4 

11

Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên \(A_1, A_2, ..., A_N\). Dãy \(C\) được gọi là dãy con tăng độ dài \(K\) của \(A\) nếu thoả mãn các điều kiện sau:

• \(K \geq 1\).
• \(1 \leq i_1 < i_2 < i_3 < ... < i_K \leq N\).
• \(C_1 = A_{i_1}, C_2 = A_{i_2}, ..., C_K = A_{i_K}\).
• \(C_1 < C_2 < ... < C_K\) nếu \(K \geq 2\)

Yêu cầu: Đếm số dãy \(C\) thoả mãn \(K\) lớn nhất có thể, tức là đếm số dãy con tăng dài nhất.

Input

• Dòng thứ nhất gồm số nguyên dương \(N\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\).

Output

• In ra số dãy con tăng dài nhất. Vì kết quả có thể rất lớn nên chỉ in kết quả sau khi lấy dư \(20071008\).

Constraints

• \(N\leq 10^5\)
• \(|A_i| \leq 10^9\)

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N\leq 10^3\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

4
2 3 5 4 

2

Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên dương \(A_1, A_2, ..., A_N\). Dãy \(C\) được gọi là dãy con tăng độ dài \(K\) của \(A\) nếu thoả mãn các điều kiện sau:

• \(K \geq 1\).
• \(1 \leq i_1 < i_2 < i_3 < ... < i_K \leq N\).
• \(C_1 = A_{i_1}, C_2 = A_{i_2}, ..., C_K = A_{i_K}\).
• \(C_1 < C_2 < ... < C_K\) nếu \(K \geq 2\)

Yêu cầu: Tìm dãy \(C\) sao cho độ dài \(K\) lớn nhất có thể. Nếu có nhiều dãy \(C\) thoả mãn, in ra dãy có thứ tự từ điển nhỏ nhất. Dãy \(C\) được gọi là dãy có thứ tự từ điển nhỏ hơn dãy \(C'\) nếu tồn tại chỉ số \(p\) \((p \geq 1)\) thoả mãn các điều kiện sau:

• \(C_1 = C'_1\), \(C_2 = C'_2\), \(...\), \(C_{p-1} = C'_{p-1}\) nếu \(p > 1\).
• \(C_p < C'_p\).

Input

• Dòng thứ nhất gồm số nguyên dương \(N\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\).

Output

• Dòng thứ nhất in ra số \(K\) là độ dài dãy con tăng \(C\) dài nhất.
• Dòng thứ hai in ra \(K\) số nguyên dương \(C_1, C_2, ..., C_N\) là dãy có thứ tự từ điển nhỏ nhất độ dài \(K\).

Constraints

• \(N \leq 10^5\)
• \(|A_i| \leq 10^9\)

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N\leq 10^3\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
1 3 5 4 6 

4
1 3 4 6

Cho một dãy \(A\) gồm \(N\) phần tử gồm các số nguyên dương \(A_1, A_2, ..., A_N\). Dãy \(C\) được gọi là dãy con BeautiQ độ dài \(K\) của \(A\) nếu tồn tại dãy chỉ số thoả mãn các điều kiện như sau:

• \(K \geq 1\).
• \(1 \leq i_1 < i_2 < i_3 < ... < i_K \leq N\).
• \(C_1 = A_{i_1}, C_2 = A_{i_2}, ..., C_K = A_{i_K}\).
• \(C_1 < C_2 < ... < C_K\) nếu \(K \geq 2\).
• \(GCD(C_1, C_2) > 1\), \(GCD(C_2, C_3) > 1\), \(...,\) \(GCD(C_{K-1}, C_K) > 1\) nếu \(K \geq 2\). (\(GCD\) tương ứng với \(UCLN\))

Yêu cầu: Tìm độ dài \(K\) lớn nhất có thể của dãy con BeautiQ \(C\).

Input

• Dòng thứ nhất chứa số nguyên dương \(N\).
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, ..., A_N\).

Output

• In ra số duy nhất là số nguyên dương \(K\).

Constraints

• \(N\leq 10^5\)
• \(A_i \leq 10^6\)

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \leq 10^5\), \(A_i < A_{i+1}\) với \(\forall{i}, 1 \leq i < N\)
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm

Example

6
9 4 5 8 7 6 

2

Giáo sư Wu Zi Mu đi thăm quan một hội trường ở Los Santos. Trong khi đi quanh thì gặp người quản lý. Người này nhờ giáo một bài toán như sau:

• Có \(N\) người muốn thuê hội trường. Người thứ \(i\) nếu thuê được hội người sẽ bắt đầu từ thời gian \(S_i\) tới thời gian \(F_i\), với chi phí \(F_i - S_i + 1\).
• Tại mỗi thời điểm hội trường chỉ được thuê bởi một người. Người \(j\) có thể thuê sau người \(i\) nếu \(F_i < S_j\).
• Người quản lý muốn làm sao để nhiều người thuê nhất có thể để lấy quan hệ. Trong trường hợp cùng số người thuê nhiều nhất thì quản lý muốn thu được nhiều chi phí nhất.
  Giáo sư Wu Zi Mu vì quên mang theo laptop, với quá nhiều người thuê, nên các bạn hãy giúp giáo sư tìm ra số người thuê nhiều nhất và chi phí nhiều nhất tương ứng.

Input

• Dòng thứ nhất chứa số nguyên dương \(N\).
• N dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(S_i, F_i\).

Output

• In ra hai số nguyên dương là người thuê nhiều nhất và chi phí nhiều nhất tương ứng.

Constraints

• \(N\leq 10^5\)
• \(S_i \leq F_i \leq 10^9\)

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N\leq 10^3\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
1 4
3 5
6 8 

2 7

Cho dãy \(A\) gồm \(N\) phần tử gồm các số nguyên dương \(A_1, A_2, ..., A_N\). Dãy \(C\) được gọi là dãy con đổi dấu độ dài \(K\) của dãy \(A\) nếu tồn tại dãy chỉ số:

• \(1 \leq i_1 < i_2 < ... < i_K \leq N\).
• Nếu \(K > 1\) thì \(C_{i_1} > C_{i_2} < C_{i_3} > ...\) hoặc \(C_{i_1} < C_{i_2} > C_{i_3} < ...\)

Yêu cầu: Tìm dãy con đổi dấu \(C\) với \(K\) lớn nhất có thể.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\).
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, ..., A_N\).

Output

• Dòng đầu tiên chứa số \(K\) là độ dài dãy con đổi dấu \(C\) dài nhất.
• Dòng thứ hai in ra \(K\) số nguyên dương \(C_1, C_2, ..., C_K\). Nếu có nhiều dãy \(C\) thoả mãn, in ra một dãy bất kỳ.

Constraints

• \(N\leq 10^5\)
• \(A_i \leq 10^9\)

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N\leq 10^3\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.
• Nếu in ra được số \(K\) là độ dài dãy con đổi dấu \(C\) dài nhất thì sẽ được \(50\%\) số điểm của test. Nếu in ra thêm được một dãy \(C\) tương ứng mà đúng thì sẽ được công thêm \(50\%\) số điểm của test.

Example

6
2 6 4 3 5 7 

4
2 4 3 5

Cho dãy \((A, B)\) gồm \(N\) phần tử là các cặp số nguyên \(A_1, A_2, ..., A_N\) và \(B_1, B_2, ..., B_N\). Dãy \((C, D)\) được gọi là dãy con tăng độ dài \(K\)của dãy \((A, B)\) nếu thoả mãn các điều kiện sau:

• \(K \geq 1\).
• \(1 \leq i_1 < i_2 < i_3 < ... < i_K \leq N\).
• \(C_1 = A_{i_1}, C_2 = A_{i_2}, ..., C_K = A_{i_K}\).
• \(D_1 = B_{i_1}, D_2 = B_{i_2}, ..., D_K = B_{i_K}\).
• \(C_1 < C_2 < ... < C_K\) nếu \(K \geq 2\).
• \(D_1 < D_2 < ... < D_K\) nếu \(K \geq 2\).

Yêu cầu: Tìm dãy \((C, D)\) thoả mãn \(K\) lớn nhất có thể, tức là tìm dãy con \((C, D)\) dài nhất.

Input

Gồm \(N + 1\) dòng:

• Dòng thứ nhất gồm số nguyên dương \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên (\(A_i, B_i\)). \((|A_i|, |B_i| \leq 10^9)\).

Output

Gồm \(K+1\) dòng:

• Dòng đầu tiên in ra số \(K\) là độ dài dãy con \((C, D)\) dài nhất.
• \(K\) dòng tiếp theo, dòng thứ \(i\) in ra hai số nguyên \(C_i, D_i\) là dãy có độ dài \(K\) dài nhất.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(N \leq 10^3\).
• Subtask \(2\) (\(25\%\) số điểm): \(N \leq 10^5\), \(|A_i|, |B_i| \leq 10^3\).
• Subtask \(3\) (\(25\%\) số điểm): \(N \leq 10^5\).
• Subtask \(4\) (\(25\%\) số điểm): \(N \leq 5.10^5\).
• Nếu xuất đúng số \(K\) sẽ được \(50\%\) số điểm của test. Nếu xuất thêm đúng dãy \((C, D)\) tương ứng thì sẽ được thêm \(50\%\) số điểm của test.

Example

5
1 5
2 3
4 5
6 8
9 9

4
2 3
4 5
6 8
9 9

Cho dãy số nguyên dương \(A = (a_1, a_2, ..., a_n)\), phần tử \(a_i\) có trọng số là \(w_i\). Mỗi dãy \((a_{i_1}, a_{i_2}, ..., a_{i_k})\) thỏa mãn:

• \(1 < i_1 < i_2 < ... < i_k < n\)
• \(a_{i_1} < a_{i_2} <... < a_{i_k}\)

được gọi là một dãy con tăng của dãy \(A\). Chú ý rằng dãy chỉ gồm duy nhất một phần tử của \(A\) cũng được gọi là một
dãy con tăng của dãy \(A\).

Yêu cầu: Trong số các dãy con tăng của dãy \(A\) hãy chỉ ra một dãy có tổng trọng số các phần tử là lớn nhất có thể.

Input

• Vào từ file văn bản IS.INP

  • Dòng \(1\) chứa số nguyên dương \(n \le 10^5\)

  • Dòng \(2\) chứa \(n\) số nguyên dương \(a_1, a_2, ..., a_n\) theo đúng thứ tự đó (\(\forall i: a_i \le 10^5\))

  • Dòng \(3\) chứa \(n\) số nguyên dương \(w_1, w_2, ..., w_n\) theo đúng thứ tự đó (\(\forall i: w_i \le 10^9\))

Output

• Ghi ra file văn bản IS.OUT

  • Dòng 1 ghi số phần tử trong dãy con tăng tìm được \((m)\)

  • Dòng 2 ghi \(m\) chỉ số của các phần tử được chọn theo thứ tự tăng đần

Các số trên một dòng của Input/Output files được/phải ghi cách nhau ít nhất một dấu cách

Example

10
1 2 3 6 4 5 9 6 7 8
11 22 33 66 44 55 999 66 77 88

6
1 2 3 5 6 7

Bạn được cho \(n\) khối lập phương theo một thứ tự nhất định, và nhiệm vụ của bạn là xây dựng các tòa tháp bằng cách sử dụng chúng. Bất cứ khi nào hai khối lập phương nằm chồng lên nhau, khối lập phương phía trên phải nhỏ hơn khối lập phương dưới.

Bạn phải xử lý các khối phương theo thứ tự được cho. Bạn luôn có thể đặt khối lập phương lên trên đỉnh của một tòa tháp hiện có hoặc bắt đầu một tòa tháp mới. Số lượng tòa tháp tối thiểu có thể là bao nhiêu?

Input

• Dòng đầu vào đầu tiên chứa một số nguyên \(n\): số lượng khối lập phương.
• Dòng tiếp theo chứa \(n\) số nguyên \(k_1,k_2,\ldots,k_n\): kích thước của các khối lập phương.

Output

• In một số nguyên: số lượng tòa tháp tối thiểu.

Constraints

• \(1 \le n \le 2 \cdot 10^5\)
• \(1 \le k_i \le 10^9\)

Example

Sample input

5
3 8 2 1 5

Sample output

2

Trong một lễ hội phim, \(n\) bộ phim sẽ được chiếu. Câu lạc bộ phim của Syrjälä bao gồm \(k\) thành viên, tất cả sẽ tham dự lễ hội phim.

Bạn biết thời gian bắt đầu và kết thúc của mỗi bộ phim. Tổng số phim tối đa mà các thành viên câu lạc bộ có thể xem hoàn toàn là bao nhiêu nếu họ hành động tối ưu?

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(k\): số lượng phim và thành viên câu lạc bộ.
• Sau này, có \(n\) dòng mô tả các bộ phim. Mỗi dòng có hai số nguyên \(a\) và \(b\): thời gian bắt đầu và kết thúc của một bộ phim.

Output

• In một số nguyên: tổng số bộ phim tối đa.

Constraints

• \(1 \le k \le n \le 2 \cdot 10^5\)
• \(1 \le a < b \le 10^9\)

Example

Sample input

5 2
1 5
8 10
3 6
2 5
6 9

Sample output

4

Một ông chủ có một phòng họp để cho thuê, có \(N\) người đến đặt họp, cuộc họp của người thứ \(i\) bắt đầu tại thời điểm \(a_i\) và kết thúc tại thời điểm \(b_i (a_i<b_i)\). Hai cuộc họp thứ \(i\) và \(j\) có thể cùng xảy ra khi \(b_i \leq a_j\) hoặc \(b_j \leq a_i\). Hãy tính xem ông chủ có thuể cho tối đa bao nhiêu người thuê phòng.

Input

• Dòng đầu tiên chứa một số nguyên dương \(N (N \leq 5000)\)
• \(N\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương \(a_i\) và \(b_i\) là thời gian bắt đầu và kết thúc của cuộc họp thứ \(i\).

Output

• Một số nguyên duy nhất là số người tối đa có thể thuê phòng.

Example

 4
8 10
10 20
2 3
13 14

3

Một ông chủ có một phòng họp để cho thuê, có \(N\) người đến đặt họp, cuộc họp của người thứ \(i\) bắt đầu tại thời điểm \(a_i\) và kết thúc tại thời điểm \(b_i (a_i<b_i)\) và người thuê sẽ trả \(c_i\) đồng cho ông chủ nếu thuê được phòng. Hai cuộc họp thứ \(i\) và \(j\) có thể cùng xảy ra khi \(b_i \leq a_j\) hoặc \(b_j \leq a_i\). Hãy tính số tiền tối đa mà ông chủ có thể nhận được.

Input

• Dòng đầu tiên chứa một số nguyên dương \(N (N \leq 5000)\)
• \(N\) dòng tiếp theo, mỗi dòng chứa 3 số nguyên dương \(a_i\), \(b_i\) và \(c_i\) là thời gian bắt đầu, kết thúc và số tiền được trả của cuộc họp thứ \(i\).

Output

• Một số nguyên duy nhất là số người tối đa có thể thuê phòng.

Example

4
8 12 6
14 15 12
5 8 5
6 14 7 

23