UVA12836

Irisss_ · 2023-06-08 20:29:07 · 题解

\blue{\mathsf{Describe}}

给定长度为 n 的数组，定义位置 i 的度数为以 i 为最高点，分别向左和向右的最长严格下降子序列的长度之和。

然后，两两合并每个位置的度数，合并两个度数分别为 x 和 y 的代价为 x+y。

求合并代价总和的最小值。

\blue{\mathsf{Solution}}

首先，预处理出每个位置向两边的最长严格下降子序列的长度，这个用正反两遍 LIS 即可解决（甚至可以直接写 O(N^2) 的），分别记为 f 和 g，每个位置的度数就是 f_i+g_i-1，减一是因为 i 这个位置会被算两遍，要减去。

然后，就是经典的石子合并问题了。

用四边形不等式优化一下即可 AC。

\blue{\mathsf{Code}}

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int n;
int f[1005], g[1005];
ll b[1005], a[1005];
ll F[1005][1005], m[1005][1005];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt;
    cin >> tt;
    for (int zeq = 1; zeq <= tt; ++zeq)  {
        cin >> n;
        for (int i = 1; i <= n; ++i) cin >> a[i];
        for (int i = 1; i <= n; ++i) f[i] = g[i] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j < i; ++j) if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
        }
        for (int i = n; i; --i) {
            for (int j = n; j > i; --j) if (a[j] < a[i]) g[i] = max(g[i], g[j] + 1);
        }
        for (int i = 1; i <= n; ++i) b[i] = f[i] + g[i] - 1;
        for (int i = 1; i <= n; ++i) a[i] = a[i - 1] + b[i];
        memset(F, 0x3f, sizeof F);
        for (int i = 1; i <= n; ++i) F[i][i] = 0, m[i][i] = i;
        for (int t = 2; t <= n; ++t) {
            for (int i = 1, j = t; j <= n; ++j, ++i) {
                for (int k = m[i][j - 1]; k <= m[i + 1][j]; ++k) {
                    if (F[i][k] + F[k + 1][j] + a[j] - a[i - 1] < F[i][j]) {
                        F[i][j] = F[i][k] + F[k + 1][j] + a[j] - a[i - 1];
                        m[i][j] = k;
                    }
                }
            }
        }
        cout << "Case " << zeq << ": " << F[1][n] << '\n';
    }

    return 0;
}
/*
f[i][j] = min(f[k][j - 1] + W(k + 1, i));
*/