#include "helpHRSiam.h"
#include "bits/stdc++.h"
using namespace std;
int a[100010];
long long dp[105][100005];
const long long inf = 1e15;
struct data {
int val;
long long dp, maxn;
data (int val, long long dp, long long maxn) {
this -> val = val;
this -> dp = dp;
this -> maxn = maxn;
}
data () {}
};
long long helpHRSiam(int N, int K, int A[]) {
for(int i = 1; i <= N; i++) {
a[i] = A[i-1];
}
memset(dp, 0, sizeof dp);
dp[0][0] = 0;
for(int i = 1; i <= N; i++) {
dp[0][i] = inf;
}
for(int i = 1; i <= K; i++) {
dp[i][0] = inf;
stack <data> Q;
for(int j = 1; j <= N; j++) {
data x;
x.val = a[j];
x.dp = dp[i - 1][j - 1];
while(!Q.empty() and Q.top().val <= a[j]) {
x.dp = min(Q.top().dp, x.dp);
Q.pop();
}
x.maxn = x.dp + x.val;
if(!Q.empty()) x.maxn = min(x.maxn, Q.top().maxn);
Q.push(x);
dp[i][j] = Q.top().maxn;
}
}
return dp[K][N];
}
int main(int argc, char const *argv[])
{
int N, K;
scanf("%d %d", &N, &K);
int *A;
A = new int [N];
for(int i = 0; i < N; i++) {
scanf("%d", &A[i]);
}
printf("%lld\n", helpHRSiam(N, K, A));
return 0;
}
Compilation message
blocks.cpp:1:24: fatal error: helpHRSiam.h: No such file or directory
#include "helpHRSiam.h"
^
compilation terminated.
