题解：P10622 [ICPC2013 WF] Matryoshka
mushezi
·
·
题解
考虑 f(l, r) 表示 [l, r] 的最小花费。
然后因为不止一组套娃所以再设 g(i) 表示前 i 个套娃拼成的最小花费。
考虑如何把两个区间拼起来，我们发现合并两组套娃的代价为它们大于对方最小套娃的套娃个数数量。
所以我们需要预处理一些东西。
$maxpos[l][r]$ 表示区间最大值的位置。
$sum[i][x]$ 相当于二维前缀和，表示从 i 位置开始的小于等于 x 的数量。
```cpp
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$ 然后拼在一起的花费。
```cpp
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));
}
```
转移方程很显然，然后注意判断区间合不合法即可。
全部代码如下。
```cpp
#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;
}
```