cíu bài chia táo
dề bài
Mẹ mới mua n quả táo cho Vũ và Long. Vì là anh nên Vũ sẽ nhường cho Long phần nhiều hơn. Tuy nhiên, Vũ sẽ lợi dụng cơ hội này để ra cho Long một bài toán về chia táo để thử thách Long:
Vũ xếp n quả táo thành 1 hàng, khối lượng các quả theo thứ tự trên hàng được thể hiện bằng mảng a:a1,a2,...,an. Long sẽ phải chia những quả táo này thành những nhóm nhỏ, sao cho mỗi nhóm sẽ gồm các quả liền kề nhau trong hàng và có tổng khối lượng của nhóm không được quá m. Với mỗi nhóm, quả có khối lượng lớn nhất sẽ thuộc về Vũ và Long sẽ được những quả còn lại.
Long ham ăn và luôn muốn ăn nhiều nhất có thể, bạn hãy giúp Long tìm ra cách chia như trên mà khối lượng táo Long có thể ăn là lớn nhất.
Input
Output
Scoring
Đáp án:
Giải thích các bước giải:
def max_apples_for_long(n, m, a):
dp = [0] * (n + 1)
for end in range(1, n + 1):
total_sum = 0
max_apple = 0
for start in range(end, 0, -1):
total_sum += a[start - 1]
if total_sum > m:
break
max_apple = max(max_apple, a[start - 1])
dp[end] = max(dp[end], dp[start - 1] + (total_sum - max_apple))
return dp[n]
n, m = map(int, input().split())
a = list(map(int, input().split()))
print(max_apples_for_long(n, m, a))
Tin học là một ngành khoa học chuyên nghiên cứu quá trình tự động hóa việc tổ chức, lưu trữ, xử lý và truyền dẫn thông tin của một hệ thống máy tính cụ thể hoặc trừu tượng. Tin học bao hàm tất cả các nghiên cứu và kỹ thuật có liên quan đến việc mô phỏng, biến đổi và tái tạo thông tin. Hãy tận dụng sức mạnh của tin học để giải quyết các vấn đề và sáng tạo ra những giải pháp mới!
Lớp 10 - Năm đầu tiên ở cấp trung học phổ thông, chúng ta sẽ có nhiều bạn bè mới đến từ những nơi khác nhau. Ngôi trường mới, xa nhà hơn, mở ra một thế giới mới với nhiều điều thú vị. Hãy mở lòng đón nhận và tận hưởng những trải nghiệm mới!
Copyright © 2021 HOCTAPSGK