\(\mathcal{Description}\)
\(n\) 个球排成一列，每个球都有自己的颜色，每个球的颜色都互不相同，且均在\([1,n]\)范围内，第 \(i\) 个球的颜色为 \(c_i\)。你需要将这些球重新排序使得第 \(i\) 个球的颜色为 \(i\)。另外，你还有 \(k\ge 1\) 个颜色为 \(0\) 的球，这些球在排序时将会用到。
由于这些球的性质特殊，你只能通过以下两种方式将他们排序：
- 将一个颜色为\(0\) 的球插入到序列中的任意一个位置。显然你只能执行这种操作 \(k\) 次，因为你只有 \(k\) 个颜色为 \(0\) 的球。
- 选择一个和零球相邻的非零球，将其取出并放到序列中的任意一个位置。每执行一次这种操作将会产生 \(1\) 的花费。
你可以以任意顺序执行这些操作，在所有操作完成后，所有颜色为 \(0\) 的球将会神奇地消失。问要使最终序列符合要求，至少要造成多少的花费。可以证明一定有解。
对所有的 \(k\in [1,n]\)求出答案。
\(\mathcal{Solution}\)
- 考虑\(0\)放在某个位置后，如果有一个数不在\(0\)旁边，并且想让这个\(0\)来取出，那么必须把之间的球都取走
- 取出的球不用管，最后再放进来即可
- 只要在若干次取球操作后，剩下的数是单增的即可
- 每次取球都是取一个区间，一个\(0\)可取一个区间
根据以上几点，可以将问题转化成
一个长度为\(n\)的排列，允许最多取走\(k\)个没有交集的连续区间，使得剩下的数是单增的，代价是取走的区间的总长度，要求代价最小是多少
考虑在最前面插入一个数大小为\(0\)，最后面插入一个数大小为\(n+1\)，这两个数最后一定会留下，因为没有取走的必要
设\(f[i][j]\)表示第\(i\)个数没有被取走，取了\(j\)个区间使得前\(i\)个数剩下单增所需最小代价
考虑转移方程，枚举\(k\in[0,i-1]\)，找到\(c[k]<c[i]\)，将\((k,i)\)之间的数全部取走
因此有当\(k<i-1\)时，\(f[i][j]=min(f[i][j], f[k][j-1]+i-k-1)\)
当\(k=i-1\)时，\(f[i][j]=min(f[i][j],f[k][j])\)
因为插入了\(n+1\)并且\(n+1\)肯定是没有被取走的，所以最后的答案就是\(f[n+1][j]\)
\(\mathcal{Code}\)
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 505;
int T, n, top;
int a[maxn];
int f[maxn][maxn];
int main()
{
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
a[n + 1] = n + 1;
memset(f, 0x3f, sizeof(f));
f[0][0] = 0;
for (int i = 1; i <= n + 1; ++i)
for (int j = 0; j <= i; ++j) {
if (j) f[i][j] = f[i][j - 1];
for (int k = 0; k < i; ++k)
if (a[k] < a[i]) {
if (k == i - 1) f[i][j] = min(f[i][j], f[k][j]);
else if (j) f[i][j] = min(f[i][j], f[k][j - 1] + i - k - 1);
}
}
for (int i = 1; i <= n; ++i) cout << f[n + 1][i] << " \n"[i == n];
}
return 0;
}
如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧