题意：有一个1~n的序列，求放k个0后，最小操作次数 ，使得去掉0后序列升序，
每次操作；可以把与0相邻的数，放到任意位置
思路：因为n最大到500 ，并且求k属于1~n的所有最小代价，所以考虑dp
dp[i][j] ,i表示以ai结尾放j个0的最小代价
最小代价等于去掉以ai结尾升序列后，剩余子段用j个区间覆盖，的最小值（最小值为j个区间的总长度），如果代价等于区间的长度则区间总可以排序成升序
转换公式：a[i-1]<a[i]->dp[i][j]=dp[i-1][j]; //如果后一位大于前一位，则直接加入以前一位结尾的升余列，花费不变。
a[k]<a[i]-> dp[i][j]=min(dp[i][j],dp[k][j-1]+(i-k-1));//这里表示，k+1，到 i-1 这个区间用 i-k-1的价值排序 ，使整体升序
代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PLL;
#define IOS cin.tie(nullptr)->sync_with_stdio(false);
#define se second
#define fi first
#define mem(a,b) memset(a,b,sizeof a);
#define pri priority_queue<int,vector<int>,greater<int> >
#define low(a,b,c) lower_bound(a,a+b,c)-a;
#define upp(a,b,c) upper_bound(a,a+b,c)-a;
const int N=1e3+7;
const int MOD = (int)1e9 + 7;
int dp[N][N];
int a[N];
void solve()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
a[n+1]=99999999;
for(int i=1;i<=n+1;i++)
{
for(int j=0;j<=n+1;j++)
{
dp[i][j]=999999999;
}
}
for(int i=1;i<=n+1;i++)
{
for(int j=0;j<=n;j++)
{
if(a[i-1]<a[i]) dp[i][j]=dp[i-1][j];
if(j)
for(int k=0;k<i;k++)
if(a[k]<a[i])
dp[i][j]=min(dp[i][j],dp[k][j-1]+i-k-1);
}
}
for(int i=1;i<=n;i++) cout<<dp[n+1][i]<<" ";
cout<<"\n";
}
int main()
{
IOS;
int t=1;
cin>>t;
while(t--)
{
solve();
}
return 0;
}