T
Cho 1 dãy số gồm N phần tử (N ≤ 10000), mỗi phần tử có 1 giá trị nằm trong khoảng [-1000, 1000]. Ban đầu, bạn sẽ ở vị trí ô số 0 với tổng điểm là 0. Mỗi nước đi, người chơi có thể di chuyển sang phải tối thiểu là 1 bước và tối đa là K bước (K ≤ 10) . Khi dừng lại ở 1 ô nào đó thì giá trị của ô đó sẽ được cộng vào tổng điểm. Bạn có thể dừng cuộc chơi bất cứ lúc nào. Hãy tìm cách chơi sao cho tổng điểm nhận được là nhiều nhất.
Dữ liệu vào
Dòng đầu tiên chứa 2 số N, K.
Dòng thứ 2 chứa N số của dãy, mỗi số cách nhau 1 dấu cách. Mỗi số nằm trong khoảng [-1000, 1000]
Dữ liệu ra
Số điểm lớn nhất có thể đạt được.
Giới hạn:
N ≤ 10000.
K ≤ 10.
Trong 20% số test có N ≤ 10
Ví dụ
Input:
5 2
-2 3 -6 -4 5
Output:
4
Giải thích:
- Ta có thể đi theo thứ tự 0 -> 2 -> 4 -> 5. Số điểm đạt được là 0 + 3 - 4 + 5 = 4.
Đây có thể coi là bài toán tìm dãy con có tổng lớn nhất. Trâu bò thì quay lui. Tối ưu nhất chắc là QHĐmời mọi người chém tiếp
Đây có thể coi là bài toán tìm dãy con có tổng lớn nhất. Trâu bò thì quay lui. Tối ưu nhất chắc là QHĐ![]()
Có bài nào cho lớp 11 không?? Có thì mới có hứng chém gió được :]
chém gió đề này nàyCó bài nào cho lớp 11 không?? Có thì mới có hứng chém gió được :]
Đang ôn thi THT thấy bài này tạm tạm post lên![]()
ĐỀ:
Khi đào hầm Thủ Thiêm người ta dùng một Robot để đào, ban đầu người ta đào đường hầm 1 đơn vị độ dài sau đó đặt Robot xuống. Robot này được điều khiển bởi 2 lệnh là: C1 v N2.
- Lệnh C1 là đào thêm 1 đơn vị độ dài thì tốn 2 đơn vị năng lượng.
- Lệnh N2 là đào thêm một đoạn đường hầm bằng độ dài đang có thì tốn 4 đơn vị năng lượng.
Hãy viết chương trình ra lệnh cho Robot đào một đường hầm có độ dài k đơn vị độ dài với các lệnh là ít nhất và sự tiêu tốn năng lượng là thấp nhất. Biết ban đầu đường hầm dài 1 đơn vị độ dài.
Yêu cầu:
- Dữ liệu vào gồm một số k là độ dài đường hầm cần đào.
- Dữ liệu ra gồm hai dòng:
+ Dòng đầu là số năng lượng ít nhất đã tiêu tốn cho Robot đào hầm.
+ Dòng tiếp theo chứa các lệnh C1 hoặc N2, mỗi lệnh cách nhau 1 khoảng trắng.
F là số năng lượng tiêu tốn ít nhất
F=min(F[i-1]+2,F[i/2]+4)
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[i1],... A[ik] thỏa mãn
i1 < i2 < ... < ik và A[i1] < A[i2] < .. < A[ik]. 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 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] (1 ≤ A ≤ 10000).
Output
Ghi ra độ dài của dãy con tăng đơn điệu dài nhất.
Ví dụ
Input:
6
1 2 5 4 6 2
Output:
4
F là độ dài dãy con đơn điệu dài nhất kết thúc tại i
F:=Max(F[j])+1, A[j]<A với j:=1->i-1
KQ bài toán là maxF với i:1->n