제출 #887265

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
887265		tigran	K blocks (IZhO14_blocks)	C++17	53 / 100	1012 ms	4696 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
int a[100005], pref[100005];
int dp[100005][105];
int main()
{
    int n, k;
    cin>>n>>k;
    dp[0][1]=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        dp[i][1]=max(a[i], dp[i-1][1]);
    }
    for(int j=2;j<=n;j++){
        for(int i=j;i<=n;i++){
            // d[i][j]=min(dp[i-1][j-1]+a[i], dp[i-2][j-1]+max(a[i-2], a[i-1]), ..., dp[j-1][j-1]+max(a[j-1], a[j-2], ..., a[i]))
            int mx=a[i];
            dp[i][j]=dp[i-1][j-1]+mx;
            for(int k=i-2;k>=j-1;k--){
                mx=max(mx, a[k+1]);
                dp[i][j]=min(dp[i][j], dp[k][j-1]+mx);
            }
        }
    }
    cout<<dp[n][k];
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 18 / 18
• Subtask 3: 21 / 21
• Subtask 4: 0 / 47