很自然想到区间 DP。
设 $Dp[i][j]$ 表示把区间 $[i, j]$ 内的套娃合并成一个所需要的代价，那么有：
- $Dp[i][i] = 0$
- $Dp[i][j] = min\{Dp[i][k] + Dp[k + 1][j] + Merge([i, k], [k + 1, j])\} (i \le k < j)$
于是问题在于算 $Merge([a, b], [c, d])$。
我们考虑一下：区间 $[a, b]$ 内的哪些套娃是需要打开的：
是不是 $[a, b]$ 中所有大于 $[c, d]$ 中最小的套娃都需要打开，来装 $[c, d]$ 中最小的套娃呢？
$[c, d]$ 同理。
于是我们可以预处理 $Sum[i][x]$ 为在前 $i$ 个套娃中，大小 $\le x$ 的套娃的个数，
那么就可以 $O(1)$ 地算 $Merge([a, b], [c, d])$ 了。
有一个问题，如果在 $[a, b]$、$[c, d]$ 中有相同大小的套娃怎么办？
不着急，先往下看。
处理完 $Dp[i][j]$ 后，我们再设立一个 $F[i]$ 表示把前 $i$ 个套娃装成若干个完好的套娃集所需代价的最小值，那么就有：
- $F[i] = min(F[j] + Dp[j + 1][i]) (mex([j + 1, i]) = i - j + 1)$
- $mex([u, v]) = min(x) (x\notin \{A_u, A_{u+1}, \dots, A_v\})$
当然，如果不能找到合法的转移点，那么令 $F[i] = INF$。
然后对于一个合法的方案，不可能出现相同大小的套娃被装进同一个套娃内的情况，
所以 $[a, b]$、$[c, d]$ 中有相同大小的套娃的话，那么这个区间一定不合法，所以我们大可不必考虑那么多了。
于是最后看 $F[n]$ 就可以了。令 $M = max\{A_i\}$
时间复杂度 $O(n^3 + n^2M)$，空间复杂度 $O(n^2 + nM)$。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 500 + 5
#define INF 593119681 int n, Max;
int A[N], _Dp[N], T[N];
int Sum[N][N], Dp[N][N], Mex[N][N], Min[N][N]; inline void Prepare()
{
for (int i = ; i <= n; i ++)
Sum[i][A[i]] ++;
for (int i = ; i <= n; i ++)
for (int j = ; j <= Max; j ++)
Sum[i][j] += Sum[i][j - ] + Sum[i - ][j] - Sum[i - ][j - ]; for (int i = ; i <= n; i ++)
{
for (int j = ; j <= Max; T[j ++] = ) ;
for (int j = i; j <= n; j ++)
{
T[A[j]] ++;
for (Mex[i][j] = ; T[Mex[i][j]]; Mex[i][j] ++) ;
Min[i][j] = i == j ? A[i] : min(Min[i][j - ], A[j]);
}
}
} inline int Calc(int l, int mid, int r)
{
int min_1 = Min[l][mid], res = Sum[r][Max] - Sum[mid][Max] - Sum[r][min_1] + Sum[mid][min_1];
min_1 = Min[mid + ][r], res += Sum[mid][Max] - Sum[l - ][Max] - Sum[mid][min_1] + Sum[l - ][min_1];
return res;
} int main()
{
#ifndef ONLINE_JUDGE
freopen("3971.in", "r", stdin);
freopen("3971.out", "w", stdout);
#endif scanf("%d", &n);
for (int i = ; i <= n; i ++)
{
scanf("%d", A + i);
Max = max(Max, A[i]);
}
Prepare();
for (int len = ; len < n; len ++)
for (int s = ; s + len <= n; s ++)
{
int i = s, j = s + len;
if (i == j) Dp[i][j] = ;
else
{
Dp[i][j] = INF;
for (int k = i; k < j; k ++)
Dp[i][j] = min(Dp[i][j], Dp[i][k] + Dp[k + ][j] + Calc(i, k, j));
}
}
for (int i = ; i <= n; i ++) _Dp[i] = INF;
for (int i = ; i <= n; i ++)
for (int j = ; j < i; j ++)
if (Mex[j + ][i] == i - j + )
_Dp[i] = min(_Dp[i], _Dp[j] + Dp[j + ][i]);
if (_Dp[n] >= INF) puts("Impossible");
else printf("%d\n", _Dp[n]); #ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
#endif
return ;
}
3971_Gromah