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] و مقدار قطعه را دوباره محاسبه می‌کنیم. [j;i].

Problem

به شما آرایه ای از n عدد صحیح داده می شود. شما باید آن را به k زیربخش غیر خالی (توالی از عناصر متوالی) تقسیم کنید تا:
1) هر عنصر آرایه دقیقاً در یک زیربخش گنجانده شده است.
2) اگر برای هر زیربخش حداقل عدد را در آن انتخاب کنیم، مجموع همه حداقل ها باید حداکثر ممکن باشد.

مجموع مینیمم مقادیر موجود در زیربخش های این پارتیشن را گزارش دهید.

ورودی:
خط اول شامل دو عدد طبیعی است - n (1 <= n <= 500) و k (1 <= k <= n).
خط دوم شامل n عدد صحیح است - عناصر آرایه ai (1 <= ai <= 105).< br / >
خروجی:
یک عدد چاپ کنید - پاسخ مشکل.

مثال:
  <بدن>
ورودی خروجی
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!