Hills

Created by LXC on Fri Mar 15 13:22:48 2024

https://codeforces.com/problemset/problem/1012/C

ranting: 1900

tag: dp

problem

给你 $n$ 个数，你一次操作可以把某一个数减一（可以减为负数），你的目标是使任意的 $k$ 个数严格大于它旁边的两个数（第一个数只用严格大于第二个数，第 $n$ 个数只用严格大于第 $n-1$ 个数），问最少需要几次操作。 $k$ 是不确定的，请输出 $k∈[1,\left\lceil\dfrac{n}{2}\right\rceil]$ 时的答案。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个正整数 $a_i$。

输出格式

一行 $\left\lceil\dfrac{n}{2}\right\rceil$ 个数，第 $i$ 个数代表 $k=i$ 时的答案

数据范围

$1≤n≤5000$

$1≤ai≤100000$

solution

动态规划

考虑基于前缀的子问题，每个前缀的状态应该包含已经有多少个”峰”，以及当前位置是否为峰。

定义$f_{i,j,k}$为前i个数，在j个峰的情况下，第i个数为峰(k=1)或不为峰(k=0)的最少操作次数。

$a_{i}$不为峰，那么$a_{i-1}$可以为峰或者不为峰。

• 对于$a_{i-1}$不为峰，我们可以直接由$f_{i-1, j, 0}$转移；
• 对于$a_{i-1}$为峰，那么$a_{i}$必须低于$a_{i-1}$，可以由$f_{i-1,j,1}+ \max(0, a_i-a_{i-1}+1)$转移。
• 取二者最小$f_{i,j,0} = \min( f_{i-1,j,0}, f_{i-1,j,1}+ \max(0, a_i-a_{i-1}+1) )$

$a_{i}$为峰，那么$a_{i-1}$必定不为峰。但是$a_{i-2}$可以为峰或不为峰

• 对于$a_{i-2}$不为峰，那么$a_{i-1}$必须低于$a_{i}$，我们可以由$f_{i-1, j-1, 0} + \max(0, a_{i-1}-a_i+1)$转移；
• 对于$a_{i-2}$为峰，那么$a_{i-1}$必须低于$a_{i}$与$a_{i-2}$，可以由$f_{i-2,j-1,1}+ \max(0, a_{i-1}-\min(a_i, a_{i-2})+1)$转移。
• 取二者最小$f_{i,j,1} = \min( f_{i-1, j-1, 0} + \max(0, a_{i-1}-a_i+1), f_{i-2,j-1,1}+ \max(0, a_{i-1}-\min(a_i, a_{i-2})+1) )$

对于需要t个峰，我们需要的最少操作应该是$\min \limits_{t \le j, 0\le k \le 1} f_{n, j, k}$

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 5005
#define MOD 998244353
#define INF 0x3f3f3f3f
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

int a[N];
int f[N][N][2];

void sol() {
    int n;
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> a[i];
    }
    memset(f, 0x3f, sizeof(f));
    int sz = (n+1)/2;
    f[0][0][0] = 0;
    for (int i=1; i<=n; i++) {
        for (int j=0; j<=sz; j++) {
            f[i][j][0] = min(f[i-1][j][0], f[i-1][j][1]+max(a[i]-a[i-1]+1, 0));
            if (j>=1) {
                f[i][j][1] = f[i-1][j-1][0]+max(a[i-1]-a[i]+1, 0);
                if (i>=2) f[i][j][1] = min(f[i][j][1], f[i-2][j-1][1]+max(0, a[i-1]-min(a[i-2], a[i])+1));
            }
            // cout << i << " " << j << ": " << f[i][j][0] << " " << f[i][j][1] << endl;
        }
    }
    int mn = INF;
    vector<int> ans;
    for (int i=sz; i>=1; i--) {
        mn = min(mn, f[n][i][0]);
        mn = min(mn, f[n][i][1]);
        ans.push_back(mn);
    }
    while (ans.size()) {
        cout << ans.back() << " ";
        ans.pop_back();
    }
    cout << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}