题目描述

霍格沃茨之战即将开始。食死徒们发明了一种使用魔杖增强力量的新方法。每个食死徒可以携带两根魔杖（左手一根，右手一根），他们站成一排组成军队的前线。每个食死徒有一个强度值，初始力量值为 $1$。

每个食死徒可以通过以下方式增加自己的力量值：

• 用左手魔杖连接左侧的另一个食死徒，要求对方的强度严格小于自己的强度，并且位置在自己左边
• 用右手魔杖连接右侧的另一个食死徒，要求对方的强度严格小于自己的强度，并且位置在自己右边

通过这种方式，食死徒可以构建一个序列：强度从左到右递增，在自己位置达到最大，然后再递减。该食死徒的力量值等于这个序列的长度，且每个食死徒都会最大化自己的力量值。

在确定所有食死徒的力量值后，赫敏需要施展分裂咒语，将整条线（或某一段）分成两部分。每次分裂的成本等于该段内所有食死徒的力量值之和。目标是通过若干次分裂，使每个食死徒都单独成段，并最小化总成本。

输入格式

• 第一行一个正整数 $T$（$T\le 300$），表示测试用例数
• 每个测试用例：
  • 第一行一个整数 $n$（$1\le n\le 1000$），表示食死徒人数
  • 第二行 $n$ 个正整数，表示从左到右的食死徒强度值（所有值小于 $10^6$）

输出格式

对每个测试用例输出 Case <x>: <y>，其中 $x$ 为用例编号（从 $1$ 开始），$y$ 为最小总成本。

题目分析

第一步：计算每个位置的力量值

对于位置 $i$，设：

• $L[i]$ 表示从位置 $i$ 向左看，强度严格递增的最长序列长度（包括 $i$ 自身）
• $R[i]$ 表示从位置 $i$ 向右看，强度严格递减的最长序列长度（包括 $i$ 自身）

那么位置 $i$ 的力量值为：
$$power[i]=L[i]+R[i]-1$$

因为 $i$ 在左边递增序列和右边递减序列中被重复计算了一次。

$\text{L}$ 数组的计算方法

对于每个 $i$，向左扫描所有 $j<i$，如果 $a[j]<a[i]$（强度严格小于自己），则：
$$L[i]=\max (L[i],L[j]+1)$$
初始值 $L[i]=1$（只有自己）。

$\text{R}$ 数组的计算方法

对于每个 $i$，向右扫描所有 $j>i$，如果 $a[j]<a[i]$（强度严格小于自己），则：
$$R[i]=\max (R[i],R[j]+1)$$
初始值 $R[i]=1$。

时间复杂度 $O(n^2)$，对于 $n\le 1000$ 可以接受。

第二步：转化为区间分割问题

已知每个位置的力量值 $power[i]$，我们需要将区间 $[1,n]$ 通过不断分裂，最终得到 $n$ 个长度为 $1$ 的区间。每次分裂一段区间 $[l,r]$ 的成本等于 ${\sum }_{k=l}^{r}power[k]$。

这是一个经典的最优二叉搜索树或矩阵链乘类型的区间 $\text{DP}$ 问题。

定义状态

设 $dp[l][r]$ 表示将区间 $[l,r]$ 分裂成单个元素所需的最小总成本。

边界条件

当区间长度为 $1$ 时，不需要分裂：
$$dp[l][l]=0$$

状态转移

对于区间 $[l,r]$（长度 $\ge 2$），选择一个分割点 $k$（$l\le k<r$），进行如下操作：

1. 将区间 $[l,r]$ 分裂成 $[l,k]$ 和 $[k+1,r]$
2. 本次分裂的成本为 $\sum _{t=l}^{r}power[t]$，记作 $sum(l,r)$
3. 之后需要继续分裂两个子区间，成本为 $dp[l][k]+dp[k+1][r]$

因此：
dp[l][r]=min⁡k=lr−1{dp[l][k]+dp[k+1][r]}+sum(l,r) dp[l][r] = \min_{k=l}^{r-1} \{ dp[l][k] + dp[k+1][r] \} + sum(l, r) dp[l][r]=k=lminr−1​{dp[l][k]+dp[k+1][r]}+sum(l,r)

朴素做法的时间复杂度

枚举区间长度 $O(n)$，枚举左端点 $O(n)$，枚举分割点 $O(n)$，总复杂度 $O(n^3)$。对于 $n\le 1000$，$n^3=10^9$，再乘上 $T\le 300$，会严重超时。

第三步：使用 $\text{Knuth}$ 优化

观察转移方程：
dp[l][r]=min⁡k=lr−1{dp[l][k]+dp[k+1][r]}+sum(l,r) dp[l][r] = \min_{k=l}^{r-1} \{ dp[l][k] + dp[k+1][r] \} + sum(l, r) dp[l][r]=k=lminr−1​{dp[l][k]+dp[k+1][r]}+sum(l,r)

其中 $sum(l,r)$ 与 $k$ 无关，可以提取出来：
dp[l][r]=min⁡k=lr−1{dp[l][k]+dp[k+1][r]}+sum(l,r) dp[l][r] = \min_{k=l}^{r-1} \{ dp[l][k] + dp[k+1][r] \} + sum(l, r) dp[l][r]=k=lminr−1​{dp[l][k]+dp[k+1][r]}+sum(l,r)

这个形式满足四边形不等式，因此可以使用 $\text{Knuth}$ 优化。

$\text{Knuth}$ 优化的核心思想

设 $K[l][r]$ 表示使 $dp[l][r]$ 取得最小值的最优分割点 $k$。对于满足四边形不等式的 $\text{DP}$，最优分割点具有单调性：
$$K[l][r-1]\le K[l][r]\le K[l+1][r]$$

这意味着当我们计算 $dp[l][r]$ 时，不需要枚举所有 $k$，只需要枚举：
$$k\in [K[l][r-1],K[l+1][r]]$$

由于每个区间 $[l,r]$ 的枚举范围均摊为 $O(1)$，总时间复杂度降为 $O(n^2)$。

初始化 $\text{K}$ 数组

对于长度为 $1$ 的区间，设置 $K[i][i]=i$（虽然不会使用，但为了方便边界条件）。

计算顺序

按照区间长度从小到大的顺序计算，保证计算 $dp[l][r]$ 时，$dp[l][r-1]$ 和 $dp[l+1][r]$ 已经计算完毕。

第四步：前缀和优化

为了快速计算 $sum(l,r)={\sum }_{t=l}^{r}power[t]$，我们预处理前缀和数组 $pre$：
$$pre[i]=\sum _{t=0}^{i-1}power[t]$$
则有：
$$sum(l,r)=pre[r+1]-pre[l]$$

算法步骤总结

1. 读入 $T$，对每个测试用例：
2. 读入 $n$ 和强度数组 $a$
3. 计算 $L$ 数组：对于每个 $i$，向左扫描找严格递增序列的最大长度
4. 计算 $R$ 数组：对于每个 $i$，向右扫描找严格递减序列的最大长度
5. 计算 $power[i]=L[i]+R[i]-1$
6. 计算 $power$ 的前缀和数组 $pre$
7. 初始化 $dp$ 数组为 $0$，$K[i][i]=i$
8. 按区间长度从小到大进行 $\text{DP}$，利用 $\text{Knuth}$ 优化缩小 $k$ 的枚举范围
9. 输出 $dp[0][n-1]$

复杂度分析

• 计算 $L$ 和 $R$：$O(n^2)$
• $\text{Knuth}$ 优化区间 $\text{DP}$：$O(n^2)$
• 总复杂度：$O(n^2)$，对于 $n\le 1000$ 可以轻松通过 $T\le 300$ 的测试数据

代码实现

// Gain Battle Power
// UVa ID: 12836
// Verdict: Accepted
// Submission Date: 2026-04-26
// UVa Run Time: 2.210s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

int main() {
    int T;
    scanf("%d", &T);
    for (int caseNo = 1; caseNo <= T; ++caseNo) {
        int n;
        scanf("%d", &n);
        vector<int> a(n);
        for (int i = 0; i < n; ++i) scanf("%d", &a[i]);

        // 计算 L[i]：向左严格递增的最长长度
        vector<int> L(n, 1), R(n, 1);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < i; ++j)
                if (a[j] < a[i]) L[i] = max(L[i], L[j] + 1);

        // 计算 R[i]：向右严格递减的最长长度
        for (int i = n - 1; i >= 0; --i)
            for (int j = i + 1; j < n; ++j)
                if (a[j] < a[i]) R[i] = max(R[i], R[j] + 1);

        // 力量值
        vector<int> power(n);
        for (int i = 0; i < n; ++i) power[i] = L[i] + R[i] - 1;

        // 前缀和
        vector<int> pre(n + 1, 0);
        for (int i = 0; i < n; ++i) pre[i + 1] = pre[i] + power[i];

        // 区间DP + Knuth优化
        vector<vector<int>> dp(n, vector<int>(n, 0));
        vector<vector<int>> K(n, vector<int>(n, 0));

        // 初始化：长度为1的区间不需要分割点
        for (int i = 0; i < n; ++i) K[i][i] = i;

        // 枚举区间长度
        for (int len = 2; len <= n; ++len) {
            for (int l = 0; l + len <= n; ++l) {
                int r = l + len - 1;
                int sumLR = pre[r + 1] - pre[l];
                dp[l][r] = INF;

                // 利用 Knuth 优化缩小 k 的范围
                int kMin = K[l][r - 1];
                int kMax = K[l + 1][r];
                for (int k = kMin; k <= kMax && k < r; ++k) {
                    int val = dp[l][k] + dp[k + 1][r] + sumLR;
                    if (val < dp[l][r]) {
                        dp[l][r] = val;
                        K[l][r] = k;
                    }
                }
            }
        }

        printf("Case %d: %d\n", caseNo, dp[0][n - 1]);
    }
    return 0;
}

总结

本题的核心难点有两个：

1. 正确理解力量值的计算方式：每个食死徒的力量值等于其左侧严格递增序列长度加上右侧严格递减序列长度减 $1$。这是一个典型的 $\text{LIS}$（最长递增子序列）变种问题。

2. 将分裂问题转化为区间 $\text{DP}$：每次分裂的成本是区间内所有力量值之和，这类似于矩阵链乘问题，但成本函数与分割点无关，因此可以使用 $\text{Knuth}$ 优化将 $O(n^3)$ 降为 $O(n^2)$。

通过这两个步骤的合理结合，即可在给定数据范围内高效求解。