526互联

[Codeforces Round 876 (Div. 2)][Codeforces 1839D. Ball Sorting]

发布时间 2023-06-10 15:33:48作者: DeaphetS

题目链接：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();
}