题目描述
给定 \(N\) 个不同颜色的小球。你可以进行以下操作:
- 插入一个颜色为 \(0\) 的小球,此操作最多执行 \(k\) 次。
- 选择一个非零球,使得该球与至少一个 \(0\) 小球相邻。并把该小球移动到任意位置。这样会花费 \(1\) 的代价。
对于每个 \(1\le k \le N\) 求出将序列变成一个去除 \(0\) 后升序的序列所需最小代价。
思路
定义 \(dp_{i,j}\) 表示把 \([1,i]\) 排序,使用 \(j\) 个 \(0\) 小球所需的最小代价。
如果 \(a_i > a_{i-1}\),那么我们有转移 \(dp_{i,j}\leftarrow dp_{i-1,j}\)。
否则,对于所有 \(0\le k < i-1且a_k<a_i\),那么我们有 \(dp_{i,j}\leftarrow dp_{k,j-1}+i-k-1\),因为此时使用了一个 \(0\) 球,并且除端点外区间中每个点都需要移动一次。
空间复杂度 \(O(N^2)\),时间复杂度 \(O(N^3)\)。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 505, INF = MAXN;
int t, n, a[MAXN], dp[MAXN][MAXN], ans;
void Solve() {
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
for(int i = 0; i <= n + 1; ++i) {
for(int j = 0; j <= n; ++j) {
dp[i][j] = INF;
}
}
dp[0][0] = 0, a[n + 1] = n + 1;
for(int i = 1; i <= n + 1; ++i) {
for(int j = 0; j <= n; ++j) {
if(a[i] > a[i - 1]) {
dp[i][j] = dp[i - 1][j];
}
if(j) {
for(int k = 0; k < i - 1; ++k) {
if(a[k] < a[i]) {
dp[i][j] = min(dp[i][j], dp[k][j - 1] + i - k - 1);
}
}
}
}
}
ans = dp[n + 1][0];
for(int i = 1; i <= n; ++i) {
ans = min(ans, dp[n + 1][i]);
cout << ans << " \n"[i == n];
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
for(cin >> t; t--; Solve()) {
}
return 0;
}
标签:le,int,1839,小球,CF,MAXN,ans,dp
From: https://www.cnblogs.com/yaosicheng124/p/18416688