Trang chủ Tin Học Lớp 10 cíu bài chia táo dề bài Mẹ mới mua nn quả táo cho Vũ và Long. Vì là anh nên...
Câu hỏi :

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

  • Dòng đầu tiên gồm 2 số nguyên n  m.
  • Dòng thứ 2 gồm n số nguyên dương thể hiện a:a1,a2,...,an.

Output

  • Hãy in ra khối lượng táo lớn nhất mà Long có thể ăn.

Scoring

  • Subtask 1 (30% số điểm): n≤103,m≤1018.
  • Subtask 2 (20% số điểm): n≤105,m≤200.
  • Subtask 3 (50% số điểm): n≤105,m≤1018.
  • Mọi test đều có ai≤min(m,106),∀i

Lời giải 1 :

Đá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))

Bạn có biết?

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!

Nguồn :

Wikipedia - Bách khoa toàn thư

Tâm sự lớp 10

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!

Nguồn :

sưu tập

Copyright © 2024 Giai BT SGK