题解：AT_abc209_f [ABC209F] Deforestation

· · 题解

可逐步展开每个 block。

::::info[block1.最小总代价如何刻画]

hint1

不要研究砍树顺序。考虑对于高度 h_i 会被计算多少次。

代价只可能从左边，右边，自己出来。那么可以将总代价写成：

\sum_{i=1} h_i \times (某个顺序相关的)

那么考虑对于两颗相邻的树 h_i 和 h_{i-1}，应该怎么决定先砍哪个？

answer1

显然是先砍大的，交换证明即可。

所以得出结论：

::::info[block2.转化成插入/相对顺序模型]

hint2

假设前 i-1 个已经完成了并构造出了合法排列，第 p_{i-1} 在 j 那个位置，现在插入进去 i，由第一部分的结论，i 应该在哪？

answer2

::::info[block3.状态定义]

hint3

都推到了第二部分了，还不能写转移方程吗？动态规划状态定义？转移方程？

answer3

定义 f_{i,j} 表示只考虑编号 1 到 i 的元素，构成合法排列且元素 i 的相对排行为 j 的方案数。

状态转移方程：

f_{i,j}=\sum_{k=j}^i f_{i-1,k},h_i > h_{i-1} f_{i,j}=\sum_{k=1}^{j-1} f_{i-1,k},h_i < h_{i-1} f_{i,j}=\sum_{k=1}^{i} f_{i-1,k},h_i = h_{i-1}

此时已经可以写出来 \Theta(n^3) 做法了。 ::::

::::info[block4.前缀和优化]

hint4

已经做出来了但是时间复杂度不行，怎么办？

answer4

注意到转移中只有加法，可以使用前缀和优化动态规划，即定义 s_{i,j}=\sum_{k=1}^j f_{i,k}，这个可以在动态规划的时候随手通过 s_{i,j}=s_{i,j-1}+f_{i,j} 转移。然后我们就可以做到 \Theta(n^2) 了。

::::

代码

#include <bits/stdc++.h>
using namespace std;
namespace hjyowl {
const long long N = 5010, mod = 1e9 + 7;
long long s[N][N], f[N][N];
long long a[N];
long long main() {
    long long n;
    cin >> n;
    for (long long i = 1; i <= n; i++) {
        cin >> a[i];
    }
    f[1][1] = 1;
    for (long long i = 1; i <= n; i++) {
        s[1][i] = 1;
    }
    for (long long i = 2; i <= n; i++) {
        for (long long j = 1; j <= i; j++) {
            if (a[i] > a[i - 1]) {
                f[i][j] = (s[i - 1][i - 1] - s[i - 1][j - 1] + mod) % mod;
            } else if (a[i] < a[i - 1]) {
                f[i][j] = s[i - 1][j - 1] % mod;
            } else {
                f[i][j] = s[i - 1][i - 1] % mod;
            }
            s[i][j] = (s[i][j - 1] + f[i][j]) % mod;
        }
    }
    long long res = 0;
    for (long long i = 1; i <= n; i++) {
        res = (res + f[n][i]) % mod;
    }
    cout << res;
    return 0;
}
}  // namespace hjyowl
int main() { return hjyowl::main(); }