Quy hoạch động 1

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 Dãy con tăng dài nhất (bản dễ) 100 (p) 1.0s 512M
2 Bài toán ba lô 1 100 (p) 2.0s 256M
3 CSES - Array Description | Mô tả mảng 100 (p) 1.0s 512M
4 Dãy con tăng dài nhất (bản khó) 100 (p) 0.7s 512M

1. Dãy con tăng dài nhất (bản dễ)

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

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.

Test 1

Input 
6
1 2 5 4 6 2
Output 
4

Nguồn: vn.spoj

2. Bài toán ba lô 1

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Có \(N\) viên bi, được đánh số \(1,2,3,...,N\). Với mỗi \(i(1\le i\le N)\), viên bi thứ \(i\) có khối lượng là \(w_i\) và có giá trị là \(v_i\).

\(Kaninho\) quyết định chọn một số viên bi từ \(N\) viên bi trên và bỏ vào ba lô để đi chơi. Sức chứa của ba lô là \(W\), có nghĩa là tổng khối lượng của các viên bi được chọn phải không được quá \(W\).

Tìm tổng giá trị lớn nhất có thể của các viên bi được chọn để bỏ vào ba lô.

Input

  • Dòng thứ nhất chứa hai số nguyên \(N,W(1\le N\le 100,1\le W\le 10^5)\)

  • \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(w_i,v_i(1\le w_i\le W,1\le v_i\le 10^9)\)

Output

  • In ra giá trị cần tìm.

Example

Test 1

Input 
3 8
3 30
4 50
5 60
Output 
90
Note

Giải thích: Viên bi thứ \(1\) và \(3\) sẽ được chọn để bỏ vào ba lô. Vì chúng có tổng khối lượng không quá \(8\) và có giá trị lớn nhất là \(90\).

3. CSES - Array Description | Mô tả mảng

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho trước một mảng độ dài \(n\) trong đó có một số vị trí chưa được xác định giá trị. Hãy đếm số cách điền giá trị vào những vị trí đó thoả mãn điều kiện sau:

  • Các giá trị trong mảng là số nguyên trong khoảng từ \(1\) đến \(m\)
  • Chênh lệch giữa hai phần tử liền kề không quá \(1\)

Input

  • Dòng đầu tiên có hai số nguyên \(n\) và \(m\): kích thước mảng và giới hạn trên cho mỗi giá trị
  • Dòng tiếp theo có \(n\) số nguyên \(x_1,x_2,\ldots,x_n\): nội dung của mảng. Giá trị \(0\) biểu thị một giá trị không xác định

Constraints

  • \(1 \leq n \leq 10^5\)
  • \(1 \leq m \leq 100\)
  • \(0 \leq x_i \leq m\)

Output

  • In một số nguyên: số lượng dãy (cũng là số lượng cách điền) chia lấy dư cho \(10^9 + 7\)

Example

Test 1

Input 
3 5
2 0 2
Output 
3
Note

Các dãy \([2, 1, 2]\), \([2, 2, 2]\), \([2, 3, 2]\) khớp với mô tả.

4. Dãy con tăng dài nhất (bản khó)

Điểm: 100 (p) Thời gian: 0.7s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một dãy số nguyên gồm \(N\) phần tử \(A[1],A[2],\cdots A[N]\).

Biết rằng dãy con tăng đơn điệu là 1 dãy \(A[i_1],\cdots A[i_k]\) thỏa mãn \(i_1<i_2< \cdots <i_k\) và \(A[i_1]<A[i_2]< \cdots <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ử.

Input

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

Output

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

Example

Test 1

Input 
6
1 2 5 4 6 2
Output 
4