自动搬运

查看原文

来自洛谷，原作者为

	mushezi 人生苦短 , 及时行乐~

搬运于2025-08-24 22:59:42，当前版本为作者最后更新于2024-11-28 19:28:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑 $f(l, r)$ 表示 $[l, r]$ 的最小花费。

然后因为不止一组套娃所以再设 $g(i)$ 表示前 $i$ 个套娃拼成的最小花费。

考虑如何把两个区间拼起来，我们发现合并两组套娃的代价为它们大于对方最小套娃的套娃个数数量。

所以我们需要预处理一些东西。

$minv[l][r]$ 和 $maxv[l][r]$ 就是区间最大/小值。

$maxpos[l][r]$ 表示区间最大值的位置。

$sum[i][x]$ 相当于二维前缀和，表示从 i 位置开始的小于等于 x 的数量。

void Init(){
    memset(g, 0x3f, sizeof(g));
    memset(f, 0x3f, sizeof(f));
    g[0] = 0;

    for(int i = 1; i <= n + 1; i++){
        f[i][i] = 0;
        minv[i][i] = arr[i];
        maxv[i][i] = arr[i];
        maxpos[i][i] = temp[i];
        for(int j = i + 1; j <= n; j++){
            minv[i][j] = min(minv[i][j - 1], arr[j]);
            maxv[i][j] = max(maxv[i][j - 1], arr[j]);
            maxpos[i][j] = max(maxpos[i][j], temp[j]);
        }
        for(int j = 1; j < N; j++){
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
    }
}

然后我们就可以实现 $cost(i, k, j)$ 表示 $[l, r]$ 这个区间，中间点为 $k$ 然后拼在一起的花费。

int getsum(int a, int b, int c, int d){
    return (sum[c][d] - sum[a - 1][d] - sum[c][b - 1] + sum[a - 1][b - 1]);
}

int cost(int i, int k, int j){
    return (getsum(i, minv[k + 1][j], k, N - 1) + getsum(k + 1, minv[i][k], j, N - 1));
}

转移方程很显然，然后注意判断区间合不合法即可。

全部代码如下。

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

const int N = 505;
const int M = 0x3f3f3f3f;

int n;
int sum[N][N], minv[N][N], maxv[N][N], maxpos[N][N];
int temp[N], l1[N], arr[N];
int pos[N], top;
int f[N][N], g[N];

// f[l, r] 表示 [l, r] 区间拼套娃组的最小花费
// g[p] 表示前 p 个套娃已经装好的最小花费

void Init(){
    memset(g, 0x3f, sizeof(g));
    memset(f, 0x3f, sizeof(f));
    g[0] = 0;

    for(int i = 1; i <= n + 1; i++){
        f[i][i] = 0;
        minv[i][i] = arr[i];
        maxv[i][i] = arr[i];
        maxpos[i][i] = temp[i];
        for(int j = i + 1; j <= n; j++){
            minv[i][j] = min(minv[i][j - 1], arr[j]);
            maxv[i][j] = max(maxv[i][j - 1], arr[j]);
            maxpos[i][j] = max(maxpos[i][j], temp[j]);
        }
        for(int j = 1; j < N; j++){
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
    }
}

int getsum(int a, int b, int c, int d){
    return (sum[c][d] - sum[a - 1][d] - sum[c][b - 1] + sum[a - 1][b - 1]);
}

int cost(int i, int k, int j){
    return (getsum(i, minv[k + 1][j], k, N - 1) + getsum(k + 1, minv[i][k], j, N - 1));
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;

        sum[i][x]++;
        arr[i] = x;
        temp[i] = l1[x];
        l1[x] = i;
    }

    Init();

    for(int len = 1; len <= n; len++){
        for(int i = 1; i + len - 1 <= n; i++){
            int j = i + len - 1;

            if(maxpos[i][j] >= i) continue;

            for(int k = i; k < j; k++){
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + cost(i, k, j));
            }
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i; j++){
            // 符合条件的才能接上去
            if(maxpos[j][i] < j && minv[j][i] == 1 && maxv[j][i] == i - j + 1){
                g[i] = min(g[i], g[j - 1] + f[j][i]);
            }
        }
    }

    if(g[n] != M) cout << g[n];
    else cout << "Impossible";

    return 0;
}