Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- const int N=3e5+5;
- int a[N];
- long long f[N][15];
- int main(){
- int tst;
- cin>>tst;
- while(tst--){
- int n, m;
- cin>>n>>m;
- for(int i=1;i<=n;i++) cin>>a[i];
- for(int i=1;i<=m;i++) f[0][i]=1e18;
- for(int i=1;i<=n;i++){
- for(int j=0;j<=m;j++)
- f[i][j]=f[i-1][j]+a[i];
- for(int val=1e9, j=0; j<=min(i-1,m); j++){
- val=min(val,a[i-j]);
- for(int k=j;k<=m;k++)
- f[i][k]=min(f[i][k],f[i-j-1][k-j]+1ll*(j+1)*val);
- }
- }
- cout<<f[n][min(n-1,m)]<<"\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement