題目鏈接：D - Ball Sorting

題目大意：需要對一個排列按照指定操作進行排序。操作一：在數字間插入一個特殊點，可執行不超過 \(k\) 次；操作二：將在特殊點旁的數移動到任意位置。所有操作結束后特殊點會消失，要求對所有 \(k\in [1,n]\)，求出操作二的最少操作次數。

分析題意可以得出，操作一放置的特殊點之作用就是將包含他在內的一個區間傳送到對應的位置。那么所有的傳送完成之后想要有序，就需要那些未被傳送區間覆蓋的位置本身構成一個上升子序列。而這些傳送的代價就是被覆蓋的區間長度之和。于是就可以考慮 \(\texttt{DP}\) ，設 \(f(i,j)\) 表示處理完前 \(i\) 個位置，放入了 \(j\) 個特殊點時的最小代價。

考慮如何具體設立狀態，注意到如果直接貪心考慮第 \(i\) 個位置被覆蓋的情況然后轉移，可能就會出現不能直接貪心的情況，如 5 4 3 1 2。此時如果直接貪，到 \(3\) 這個位置時會直接選擇把 \(\{4,3\}\) 覆蓋掉，把 \(5\) 作為上升子序列的一部分，而最優的方案則是把 \(\{1,2\}\) 作為未被覆蓋的位置，那么就需要令 \(f(3,1)=3\)，這是不太好在轉移過程中處理的。于是我們令 \(f(i,j)\) 表達的含義為，當 \(i\) 作為上升子序列中的一部分時，放入 \(j\) 個特殊點的最小代價。

考慮如何轉移，這時我們發現實際上和最長上升子序列的轉移形式差不多。直接枚舉上一個未被覆蓋位置 \(K\) 即可，需要保證 \(a_K<a_i\)。此時若 \(K<i-1\) 則表示中間出現了被覆蓋的區間，對應代價為 \(f(K,j-1)+i-K-1\)，否則代價為 \(f(i-1,j)\)，表示目前仍未放置新的特殊點。

初始令 \(f(0,0)=0,a_{n+1}=n+1\)，最終 \(f(n+1,k)\) 即為答案。

#include<bits/stdc++.h>
using namespace std;
#define N 550
int T,n,a[N],f[N][N];
void init()
{
	scanf("%d",&n);
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	a[n+1]=n+1;
	f[0][0]=0;
	for(int i=1;i<=n+1;i++)
	for(int j=0;j<=i;j++){
		if(j)f[i][j]=min(f[i][j],f[i][j-1]);
		for(int k=i-1;k>=0;k--)if(a[k]<a[i])
			if(k==i-1)f[i][j]=min(f[i][j],f[i-1][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++)printf("%d%c",f[n+1][i],i<n?' ':'\n');
}
int main()
{
	scanf("%d",&T);
	while(T--)init();
}