1 条题解

  • 0
    @ 2026-11-12 21:57:45

    [N] Slimes(dp_n)题解

    题意简述

    NN 只史莱姆排一列,大小 aia_i。每次合并相邻两只,代价为新大小,求合并成一体的最小总代价。

    思路

    状态

    设 fl,rf_{l,r} = 把区间 [l,r][l, r] 合并成一只史莱姆的最小代价。

    转移

    最后一次合并必是把 [l,m][l, m] 与 [m+1,r][m+1, r] 合并(l≤m<rl \le m < r)。合并后大小是区间和 S(l,r)S(l,r),而两个子区间各自的内部代价是 fl,m+fm+1,rf_{l,m} + f_{m+1,r}:

    $$f_{l,r} = \min_{l \le m < r}\left( f_{l,m} + f_{m+1,r} \right) + S(l,r),$$

    fl,l=0f_{l,l} = 0,S(l,r)S(l,r) 用前缀和 O(1)O(1) 求。

    为什么正确

    任何合并方案都对应一棵"合并二叉树",其最后一次合并一定把序列切成左右两段——这正对应了枚举 mm 的所有情形,且左右两段独立最优(最优子结构)。

    复杂度

    时间 O(N3)≤40036≈1.1×107O(N^3) \le \frac{400^3}{6} \approx 1.1\times10^7,空间 O(N2)O(N^2)。

    参考代码

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    
    static long long pre[405], f[405][405];
    
    int main() {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            long long a;
            scanf("%lld", &a);
            pre[i] = pre[i - 1] + a;
        }
        for (int len = 2; len <= n; len++)
            for (int l = 1; l + len - 1 <= n; l++) {
                int r = l + len - 1;
                long long best = (1LL << 62);
                for (int m = l; m < r; m++)
                    best = min(best, f[l][m] + f[m + 1][r]);
                f[l][r] = best + pre[r] - pre[l - 1];
            }
        printf("%lld\n", f[1][n]);
        return 0;
    }
    

    易错点

    1. 代价是"合并后的和",所以要加 S(l,r)S(l,r),不是 al+ara_l + a_r。
    2. 长度从 22 开始枚举(fl,l=0f_{l,l}=0 已初始)。
    3. best 初值要足够大(用 1LL<<62),别用 INT_MAX。
    4. 10910^9 级别的 aia_i 累加后代价可达 4×10114\times10^{11},必须 long long。

    数据说明

    共 17 组:4 组官方样例(含 5×1095\times10^9);N=2N=2 的相同与最大值;N=3N=3 全相同与 109,1,10910^9,1,10^9;N=10N=10 随机;N=50/100/200/400N=50/100/200/400 随机;N=400N=400 全 11、递增、小值随机、{1,109}\{1,10^9\} 两值随机,覆盖最坏复杂度与溢出。

    • 1

    信息

    ID
    23
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    递交数
    1
    已通过
    1
    上传者