# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
99924 | MohamedAhmed0 | 동굴 (IOI13_cave) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
int dp[105][105][7] ;
int arr[105] ;
int n , k ;
int solve(int idx , int idx2 , int cnt)
{
if(cnt > k)
return 1e9 ;
if(idx == n)
{
if(cnt != k)
return 1e9 ;
return arr[idx2] ;
}
int &ret = dp[idx][idx2][cnt] ;
if(ret != -1)
return ret ;
if(idx == 0)
{
ret = solve(idx+1 , 0 , 1) ;
return ret ;
}
ret = solve(idx+1 , idx , cnt+1) + arr[idx2] ;
if(arr[idx] > arr[idx2])
idx2 = idx ;
ret = min(ret , solve(idx+1 , idx2 , cnt));
return ret ;
}
int main()
{
memset(dp , -1 , sizeof(dp));
scanf("%d %d" , &n , &k) ;
for(int i = 0 ; i < n ; ++i)
cin>>arr[i] ;
return cout<<solve(0 , 0 , 0)<<"\n" , 0 ;
}