Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 5e3 + 128;
- const int K = (N + 1) / 2;
- int dp[N][K][2];
- int p[N][K][2][3];
- int A[N];
- const int INF = 1e9;
- void solve() {
- int n;
- cin >> n;
- for (int i = 1; i <= n; i++)
- cin >> A[i];
- for (int i = 0; i <= n; i++)
- for (int j = 0; j <= (n + 1) / 2; j++)
- for (int k = 0; k < 2; k++)
- dp[i][j][k] = INF;
- dp[0][0][0] = dp[0][0][1] = 0;
- for (int i = 1; i <= n; i++) {
- for (int j = 0; j <= (n + 1) / 2; j++) {
- p[i][j][0][0] = i - 1;
- p[i][j][0][1] = j;
- if (dp[i-1][j][0] < dp[i-1][j][1]) {
- dp[i][j][0] = dp[i-1][j][0];
- p[i][j][0][2] = 0;
- } else {
- dp[i][j][0] = dp[i-1][j][1];
- p[i][j][0][2] = 1;
- }
- }
- int needLeft = 0;
- if (i > 1)
- needLeft += max(0, A[i - 1] - A[i] + 1);
- int needRight = 0;
- if (i < n)
- needRight += max(0, A[i + 1] - A[i] + 1);
- for (int j = 1; j <= (n + 1) / 2; j++) {
- p[i][j][1][0] = i - 1;
- p[i][j][1][1] = j - 1;
- p[i][j][1][2] = 0;
- if (j == 1 || i <= 2 || p[i-1][j-1][0][0] != i - 2 || p[i-1][j-1][0][1] != j - 1 || p[i-1][j-1][0][2] != 1) {
- dp[i][j][1] = dp[i-1][j-1][0] + needLeft + needRight;
- } else {
- int val = min(A[i - 1], A[i - 2] - 1);
- // A[i - 1] = val
- int exNeed = max(0, val - A[i] + 1);
- dp[i][j][1] = dp[i-1][j-1][0] + exNeed + needRight;
- }
- }
- }
- for (int i = 1; i <= (n + 1) / 2; i++) {
- cout << min(dp[n][i][0], dp[n][i][1]) << ' ';
- }
- }
- main() {
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement