也许更好的阅读体验
个球排成一列，每个球都有自己的颜色，每个球的颜色都互不相同，且均在
范围内，第
个球的颜色为
。你需要将这些球重新排序使得第
个球的颜色为
。另外，你还有
个颜色为
由于这些球的性质特殊，你只能通过以下两种方式将他们排序：
- 将一个颜色为
的球插入到序列中的任意一个位置。显然你只能执行这种操作
次，因为你只有
- 选择一个和零球相邻的非零球，将其取出并放到序列中的任意一个位置。每执行一次这种操作将会产生
你可以以任意顺序执行这些操作，在所有操作完成后，所有颜色为
对所有的 求出答案。
- 考虑
- 取出的球不用管，最后再放进来即可
- 只要在若干次取球操作后，剩下的数是单增的即可
- 每次取球都是取一个区间，一个
根据以上几点，可以将问题转化成
一个长度为的排列，允许最多取走
个没有交集的连续区间，使得剩下的数是单增的，代价是取走的区间的总长度，要求代价最小是多少
考虑在最前面插入一个数大小为，最后面插入一个数大小为
，这两个数最后一定会留下，因为没有取走的必要
设表示第
个数没有被取走，取了
个区间使得前
个数剩下单增所需最小代价
考虑转移方程，枚举，找到
，将
之间的数全部取走
因此有当时，
当时，
因为插入了并且
肯定是没有被取走的，所以最后的答案就是
#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;
}如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧