Module: الأنماط في البرمجة الديناميكية


Problem

3 /7


مجموع الانخفاضات

Theory Click to read/hide

إذا كان من الضروري تقسيم المصفوفة إلى مقاطع فرعية k بالضبط ، فسيتم إضافة المعلمة الثانية ببساطة في البرمجة الديناميكية - كم عدد المقاطع التي يجب تقسيمها.
أي ، سننظر الآن في dp التالي:
dp [i] [j] هو إجابة عناصر i الأولى ، إذا قسمناها إلى مقاطع j بالضبط.
احترس من الحالات غير الصالحة.

إعادة حساب الديناميكيات هي نفسها ، ولكن مع الأخذ في الاعتبار المعلمة الثانية. بمعنى ، عد dp [i] [k] والفرز عبر الحد الأيسر لآخر جزء فرعي j ، نعيد حساب dp [i] [k] خلال dp [j - 1] [k - 1] وقيمة المقطع [ي ؛ ط].

Problem

يتم إعطاؤك مجموعة من الأعداد الصحيحة n. تحتاج إلى تقسيمها إلى أقسام فرعية غير فارغة (سلسلة من العناصر المتتالية) بحيث:
1) تم تضمين كل عنصر من عناصر المصفوفة في جزء فرعي واحد بالضبط.
2) إذا اخترنا لكل شريحة فرعية أقل عدد فيها ، فيجب أن يكون مجموع كل الحدود الدنيا هو أقصى حد ممكن.

اذكر مجموع القيم الدنيا في الأجزاء الفرعية لهذا القسم.

الإدخال:
يحتوي السطر الأول على رقمين طبيعيين - n (1 & lt؛ = n & lt؛ = 500) و k (1 & lt؛ = k & lt؛ = n).
السطر الثاني يحتوي على n أعداد صحيحة - عناصر المصفوفة a i (1 & lt؛ = a i & lt؛ = 10 5 ). < ر />
الإخراج:
طباعة رقم واحد - الجواب على المشكلة.

مثال:
نبسب ؛ <الجسم>
إدخال الإخراج
5 3
4 2 5 1 3 		8

الشرح:
أحد الأقسام المناسبة: [4 ، 2] ، [5] ، [1 ، 3]. مجموع الحد الأدنى في كل مقطع فرعي هو 2 + 5 + 1 = 8.

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!