DP cơ bản
Điểm: 10
Có một con ếch ở bậc ~0~ muốn lên bậc ~n~. Mỗi lần ếch có thể nhảy ~1~ hoặc ~2~ bậc.
Hãy tính số cách khác nhau để ếch lên đúng bậc ~n~
Kết quả có thể rất lớn nên chỉ cần in ra phần dư sau khi chia cho ~10^9+7~
Input
- Một số nguyên ~n~ trong đó ~0 \le n \le 10^7~
Output
- Số cách ~\text{mod } 10^9+7~.
Ví dụ
Input
4
Output
5
Điểm: 10
Cầu thang có các bậc từ ~1~ đến ~n~. Có ~k~ bậc bị hỏng, ếch không được đứng lên các bậc này.
Ếch xuất phát ở bậc ~0~ (không hỏng), mỗi lần nhảy ~1~ hoặc ~2~ bậc.
Hãy đếm số cách để lên đúng bậc ~n~ theo modulo ~10^9+7~.
Bậc ~n~ đảm bảo không hỏng.
Input
- Dòng 1: ~n, k~ ~1 \le n \le 10^7,0 \le k \le 2\cdot 10^5~
- Dòng 2: ~k~ số nguyên là các bậc hỏng (có thể không tăng, có thể lặp).
Output
- Số cách lên bậc ~n~ ~\text{mod } 10^9+7~.
Ví dụ
Input
7 2
2 5
Output
3
Điểm: 10
Bạn có ~m~ loại tiền xu, mệnh giá lần lượt là ~a_1, a_2, \dots, a_m~.
Mỗi loại được dùng không giới hạn.
Hãy tìm số xu ít nhất để đổi được đúng số tiền ~S~.
Nếu không thể đổi đúng, in ra ~-1~.
Input
- Dòng 1: ~m, S~ trong đó ~1 \le m \le 100, 0 \le S \le 10^6~
- Dòng 2: ~m~ số nguyên dương ~a_i~ ~(1 \le a_i \le 10^6)~
Output
- Số xu ít nhất, hoặc ~-1~.
Ví dụ
Input
3 11
1 5 7
Output
3
Điểm: 10
Có ~n~ đồ vật.
Vật thứ ~i~ có khối lượng ~w_i~ và giá trị ~v_i~.
Bạn có chiếc ba lô sức chứa tối đa ~W~. Mỗi đồ vật chọn hoặc không chọn (0/1).
Hãy tính tổng giá trị lớn nhất có thể mang theo mà tổng khối lượng không vượt quá ~W~.
Input
- Dòng 1: ~n, W~ trong đó ~1 \le n \le 2000,1 \le W \le 2\cdot 10^5~
- ~n~ dòng tiếp theo: mỗi dòng gồm ~w_i, v_i~ trong đó ~1 \le w_i \le W,0 \le v_i \le 10^9~
Output
- Một số nguyên: giá trị lớn nhất.
Ví dụ
Input
3 7
3 4
4 5
2 3
Output
9
Điểm: 10
Cho dãy ~a_1, a_2, \dots, a_n~. Hãy tìm độ dài của dãy con tăng nghiêm ngặt dài nhất (LIS).
Input
- Dòng 1: ~n~ trong đó ~1 \le n \le 5000~
- Dòng 2: ~n~ số nguyên ~a_i~ trong đó ~|a_i| \le 10^9~
Output
- Một số nguyên: độ dài LIS.
Ví dụ
Input
8
3 1 2 1 8 5 6 2
Output
4
Điểm: 10
Cho ma trận ~n \times m~ gồm các số nguyên không âm ~c_{i,j}~ (chi phí khi đi vào ô đó).
Bạn bắt đầu ở ô ~(1,1)~ và muốn đến ~(n,m)~.
Mỗi bước chỉ được đi sang phải hoặc xuống dưới.
Tổng chi phí đường đi bằng tổng các ~(c_{i,j})~ của các ô đi qua (kể cả ô đầu và ô cuối).
Hãy tìm tổng chi phí nhỏ nhất.
Input
- Dòng 1: ~n, m~ trong đó ~(1 \le n,m \le 2000)~
- Tiếp theo ~n~ dòng, mỗi dòng ~m~ số ~c_{i,j}~ trong đó ~0 \le c_{i,j} \le 10^6~
Output
- Chi phí nhỏ nhất để đi từ ~(1,1)~ đến ~(n,m)~.
Ví dụ
Input
3 4
1 3 1 2
1 5 1 1
4 2 1 3
Output
8