#include<bits/stdc++.h>
using namespace std;
int a[100001];
int dp[10001][101];
int main(){
int n,K;
cin>>n>>K;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++) for(int j=1;j<=K;j++) dp[i][j]=INT_MAX;
for(int i=1;i<=n;i++) dp[i][1]=max(dp[i-1][1],a[i]);
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
int mx=-1;
for(int k=j;k<=i;k++) mx=max(mx,a[k]);
for(int k=2;k<=min(i,K);k++){
if(j>1)
dp[i][k]=min(dp[i][k],dp[j-1][k-1]+mx);
}
}
}
cout<<dp[n][K];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |