CF1839D题解

• 分析

  啊这道题就做得很难受了……

  手玩一下样例，不难发现答案就是分出\(k\)段不是单调上升序列的序列，求这些序列的最小长度和。
  显然有状态\(f_{l,r,k}\)表示\([l,r]\)序列分成\(k\)段的最小长度和。
  转移很好想，即枚举\(x\)，\(y\)分别表示左区间的右端点以及段数，空间复杂度\(\mathcal{O(n^3)}\)，时间复杂度\(\mathcal{O(n^5)}\)，显然不行。

  对于这种状态中存在取的数量的题目有一个常见trick，就是假设最后一个必取然后根据上一个转移，所以这样状态就变成了\(f_{l,r,k}\)表示必取r在最后一段端点的最小长度和，转移就枚举一个\(x\)即可。

  然后还要优化一维，我们发现我们转移时右区间的答案只会等于\(x+1\sim r-1\)这个区间的大小（当且仅当\(a_{x}<a_{r}\)时），除此之外没有任何值，不需要任何决策就能确定，所以我们只需要算左区间就行了，这样就能把这个区间DP优化为线性DP。
  线性DP的状态\(f_{r,k}\)表示右端点为\(r\)，分\(k\)段的最小长度和，转移同上，这样空间复杂度为\(\mathcal{O(n^2)}\)、时间复杂度为\(\mathcal{O(n^3)}\)，可以通过本题。

  然后我们发现可能有时候最优的决策\(r\)不是最后一段的端点而是就在最后一段，所以我们的答案是\(\min(\min_{i=1}^{r-1}f_{i,k-1}+r-i,f_{n,k})\)。

  边界条件是\(k<0\)不合法，\(k=0\)如果到\(r\)为止是单调上升的，那么合法，否则不合法。
  想到可能一个数的前缀都比他大，这时显然可以划出一个从第一个数到这个数的序列，但是根据我们的转移条件无法转移，所以将最小的\(r\)确定为0（或者可以看做一个数\(x\)转移的不是单调上升子序列区间为\(x+1\)到\(r-1\)，而\(x+1\)最小值为1，所以\(x\)的最小值为\(0\)），当\(r=0\)时，值也为0。

• 代码

#include <iostream>
using namespace std;
constexpr int MAXN(507);
constexpr int INF(0x3f3f3f3f);
int vis[MAXN][MAXN], f[MAXN][MAXN];
int a[MAXN];
int T, n;
inline void read(int &temp) { cin >> temp; }
int dfs(int r, int x) {
	if (x < 0)  return INF;
	if (vis[r][x])  return f[r][x];
	vis[r][x] = 1;
	if (r == 0)  return 0;
	int res(INF);
	for (int i(0); i < r; ++i) {
		if (a[i] < a[r] && i != r - 1)  res = min(res, dfs(i, x - 1) + (r - 1) - (i + 1) + 1);
		else if (a[i] < a[r])  res = min(res, dfs(i, x));
	}
	return f[r][x] = res;
}
inline void work() {
	for (int i(0); i <= n; ++i)
		for (int j(0); j <= n; ++j)  vis[i][j] = f[i][j] = 0;
	read(n);
	for (int i(1); i <= n; ++i)  read(a[i]);
	for (int i(1); i <= n; ++i) {
		int ans = dfs(n, i);
		for (int j(1); j < n; ++j)  ans = min(ans, dfs(j, i - 1) + n - j);
		cout << ans << " ";
	}
	cout << endl;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	read(T);
	while (T--)  work(); 
	return 0;
}