题目

https://ac.nowcoder.com/acm/contest/33194/I

思路

• 题目大意就是，给一个长为 n 的序列，要把它分成 k 段连续序列，每一段的代价是这一段中的最大值。分别对 k=1, 2, …, n，问最少代价。
• 令 f[i][j] 代表前 i 个数，分成 j 段的最少代价。那么会有如下一个朴素的动态规划：
• f [ i , j ] = min ⁡ 1 ≤ x < i { f [ x , j − 1 ] + max ⁡ x ≤ k ≤ i a [ k ] } f[i, j] = \min_{1 \le x < i} \{ f[x, j-1] + \max_{x \le k \le i}a[k] \} f[i,j]=1≤x<imin​{f[x,j−1]+x≤k≤imax​a[k]}
• 上面这个可以说是 O(n^3) 的，考虑如何优化。
• 对于 dp[i][j] 我们考虑序列中在 a[i] 左边第一个大于 a[i] 的数 a[t]，那么在上面的递推式中，
  • x > t 时，右半部分 max 取值都为 a[i]，最优就变成这个区间内的 f 最小值；（相当于最右边那一段是以 a[i] 为最高的）
  • x <= t 时，其实就是 f[t, j]。 （相当于 a[i] 被原来的最右边那一段吸收了）
• x>t 那部分，可以用单调栈维护左边第一个大于它的位置以及该区间内的 f 最小值。
• 总的时间复杂度是 O(n^2)

代码

#include 
using namespace std;

#define MAXN (8005)

const int INF = 1000000000;

int n;
int a[MAXN];
int f[MAXN][MAXN];
int tmp;


void solve()
{
    scanf("%d", &n);
    for (int i=1; i<=n; i++) scanf("%d", &a[i]);
    a[0] = INF;
    for (int i=0; i<=n; i++) for (int j=0; j<=n; j++) f[i][j]=INF;

    f[0][1]=0;
    for (int i=1; i<=n; i++) f[i][1]=max(f[i-1][1],a[i]);

    for (int j=2; j<=n; j++) {
        stack<pair<int, int>> st;
        //f[j][j]=f[j-1][j-1]+a[j];
        st.push({f[j-1][j-1], 0});
        st.push({INF, j-1});
        for (int i=j; i<=n; i++) {
            tmp=INF;
            while (!st.empty() && a[st.top().second]<=a[i]) {
                auto o = st.top();
                st.pop();
                tmp = min(tmp, o.first);
            }
            auto o = st.top();
            st.pop();
            tmp = min(tmp, o.first);

            f[i][j] = min(f[o.second][j], tmp+a[i]);
            f[i][j] = min(f[i][j], f[i-1][j-1] + a[i]);

            o.first = min(tmp, f[i][j-1]);
            st.push(o);
            st.push({INF, i});
        }
    }

    for (int i=1; i<=n; i++) {
        printf("%d\n", f[n][i]);
    }
}


int main()
{
    //freopen("1.txt", "r", stdin);
    solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60