#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define FAST ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
const int MOD = 1e9 + 7;
const int MOD1 = 998244353;
const int LOG = 20;
const int INF = 1e9+7;
template<class X, class Y>
bool minimize(X &x, const Y &y) {
if (x > y)
{
x = y;
return true;
}
return false;
}
template<class X, class Y>
bool maximize(X &x, const Y &y) {
if (x < y)
{
x = y;
return true;
}
return false;
}
int dx [] {-1, 1, 0, 0};
int dy [] {0, 0, 1, -1};
/* Authors: Nguyen Minh Huy from Le Quy Don high school for Gifted Students */
#define MAX 100005
int a[MAX], n, k;
int dp[105][MAX];
void read() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
}
/*
F(i, j) xét đến i số và chia j nhóm
F(i, j) = min(F(k, j - 1) + max(ak, .. ai));
*/
/* đảo nhãn lại
F(i, j) chia i nhóm xét đến j số
F(i, j) = min(F(i - 1, k) + max(ak, ... aj))
*/
void solve() {
for (int i = 1; i <= k; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = INF;
}
}
for (int i = 1; i <= k; i++) {
stack<int> q;
for (int j = 1; j <= n; j++) {
int tmp = dp[i - 1][j - 1];
while (!q.empty() && a[q.top()] < a[j]) {
minimize(tmp, dp[i - 1][q.top()]);
q.pop();
}
minimize(dp[i][j], tmp + a[j]);
minimize(dp[i][j], q.empty() ? INF : dp[i][q.top()]);
//cout << dp[i][j] << endl;
q.push(j);
}
}
cout << dp[k][n];
}
/* Don't coppy :D */
int main(){
//freopen("TASK.inp", "r", stdin);
//freopen("TASK.out", "w", stdout);
FAST;
read();
solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |