Cho mảng số nguyên A[] gồm N phần từ, hãy tìm dãy con (không nhất thiết các phần tử phải liên tiếp) tăng chặt dài nhất của mảng A[].

Đầu vào: Dòng đầu tiên là N; Dòng thứ 2 gồm N phần tử của mảng A

Ràng buộc: 1<=N<=1000; 1<=A[i]<=1000;

Đầu ra: In ra độ dài của dãy con tăng dài nhất

Input:

14
128 104 53 876 660 961 754 775 290 231 224 915 392 994

Output:

6

Cho dãy số A[] gồm N số. Nhiệm vụ của bạn là tìm tổng lớn nhất của dãy con được sắp theo thứ tự tăng dần của dãy A. Ví dụ với dãy A[] = (1, 101, 2, 3, 100, 4, 5} ta có kết quả là 106 = 1 + 2 + 3 + 100. Với dãy A[] = {10, 7, 5} ta có kết quả là 10. Với dãy A[] = {1, 2, 3, 5} ta có kết quả là 11.

Đầu vào: Dòng đầu tiên đưa vào N là số phần tử của dãy A[]; Dòng tiếp theo đưa vào N số A[i]; các số được viết cách nhau một vài khoảng trồng.

Ràng buộc: 1≤N≤1000; 0≤A[i]≤1000.

Đầu ra: Đưa ra kết quả của bài toán trên 1 dòng

Input:

8
2 12 3 15 3 16 12 4

Output:

45

Cho mảng A[] gồm N phần tử, nhiệm vụ của bạn là tính tổng lớn nhất của dãy con trong mảng với một điều kiện đó là trong dãy con này không được có 2 phần tử năm liền kề nhau.

Đầu vào: Dòng đầu tiên là N là số lượng phần tử trong mảng: Dòng thứ 2 là A[i]

Ràng buộc: 1<=N<=10^6; 1<=A[i]<=1000;

Đầu ra: In ra kết quả của bài toán

Input:

7
1 1 1 4 1 1 100

Output:

105

Input:

7
314 514 148 451 896 589 296

Output:

1706

Cho 2 xâu kí tự S và T, hãy tìm xâu con chung dài nhất của S và T. Các kí tự của xâu con không nhất thiết phải liền kề nhau.

Đầu vào: Dòng đầu tiên là xâu S; Dòng thứ 2 là xâu T;

Ràng buộc: S và T chỉ gồm các chữ cái in hoa và có độ dài không quá 1000

Đầu ra: In ra độ dài xâu con chung dài nhất của S và T

Input:

ZHFTDFHF
TFISHROV

Output:

3

Giải thích: Đó chính là xâu TFH

Một tên trộm có 1 cái túi có thể mang các đố vật với trọng lượng tối đa là V. Hiện tại tên trộm muốn lựa chọn các đồ vật trong N đồ vật để ăn trộm, mỗi đồ vật có trọng lượng là w[i] và giá trị là v[i]. Hãy xác định tổng giá trị lớn nhất của các đồ vật mà tên trộm này lựa chọn sao cho trọng lượng của chúng không vượt quá V.

Đầu vào: Dòng đầu ghi 2 số N và V. Dòng tiếp theo ghi N số của mảng w[]. Sau đó là một dòng ghi N số của mảng v[].

Ràng buộc: V<=1000; N≤1000; 1<=w[i], c[i]<=500;

Input 01:

6 22
39 44 4 59 91 70
47 26 92 33 6 69

Output 01:

92

Input 02:

6 25
7 4 5 6 9 2
12 4 6 12 11 4

Output 02:

39

Cho mảng số nguyên A[] gồm N phần tử và số nguyên dương S, nhiệm vụ của bạn hãy xác định xem có thể tạo ra một tập con các phần tử trong mảng có tổng băng S hay không? Chú ý mỗi phần tử trong mảng chỉ được sử dụng một lần.

Đầu vào: Dòng đầu tiên gồm 2 số N và S; Dòng thứ 2 gồm N số của mảng A;

Ràng buộc: 1<=N<=200; 1<=S<=50000; 1<=A[i]＜=500

Đầu ra: In ra 1 nếu có tập con của A có tổng băng S, ngược lại in ra 0

Input:

8 92
69 16 82 170 31 24 45 112

Output:

1

Hãy xem xét một hệ thống tiền tệ của ngân hàng XYZ bao gồm n đồng xu. Mỗi đồng xu có một giá trị nguyên dương. Nhiệm vụ của bạn là tính số cách riêng biệt mà bạn có thể tạo ra số tiền x bằng cách sử dụng số xu có sẵn. Ví dụ: nếu số xu là (2,3,5) và tổng mong muốn là 9, có 8 cách: 2 + 2 + 5; 2 + 5 + 2; 5 + 2 + 2; 3 + 3 + 3; 2 + 2 + 2 + 3; 2 + 2 + 3 + 2; 2 + 3 + 2 + 2; 3 +2 + 2 + 2;

Đầu vào: Dòng tiên có hai số nguyên n và x là số xu và số tiền mong muốn. Dòng thứ hai có n số nguyên phân biệt c1, c2,..., cn là giá trị của mỗi đồng xu.

Ràng buộc: 1 <= n <= 100; 1 <= x <= 10^6; 1 <= ci<= 10^6;

Đầu ra: In ra kết quả lấy dư với 10^9 + 7

Input:

3 9
2 3 5

Output:

8