在pta可以补题。

题目大意 / Problem

给定一个不降序列，每次可以中间的元素（除了第一个和最后一个元素）进行一次操作：

先选择一个点删除，然后选一个点设置为任意的值。

过程中需要保证序列一直是不降的，序列的权值是所有相邻的元素的差的平方和（第一个和最后一个不相邻）。

问k次修改可以使得权值最大为多少。

思路 / Thought

发现修改点和删除点是一样的。比如在一个长度为9的序列中，可以操作2次，其实可以在中间5个元素中任选4个，一定有一种合法的顺序使得这4个都被删除（2个删除，2个移动到和相邻元素相等）。

所以可以看出一个状态：dp[i][j]表示到第i位为止，在[2, i - 1]中删除了j个元素之后的的最大权值。

接下来就是考虑转移：对于一个区间[1, t]，我们在[2, t - 1]中任选k个点删除，只有两种情况：

1.全部删除

2.部分删除，中间一定有一个点是保留下来的

我们就只需要枚举最右侧保留的点i就好了，如果是全部删除，意味着保留点是1。那么保留点左侧[1, i]的通过dfs继续递归，[i + 1,t - 1]的全部删除（因为是最右侧的保留点）。

写一个记忆化搜索的dp。

注意cnt不能超过k或者是负数。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 103;
int a[maxn], dp[maxn][maxn];

int dfs(int t,int k)//[1, t]，删除k个点 
{
	if(dp[t][k] ^ -1)return dp[t][k];
	int res = 0;
	
	for(int i = t - 1;i >= 1; -- i)
	{
		//[i + 1, t - 1]全删，[1, i]继续递归
		int cnt = (t - 1) - (i + 1) + 1;
		if(cnt > k || cnt < 0)continue;
		res = max(res, dfs(i, k - cnt) + (a[t] - a[i]) * (a[t] - a[i]));
	}
	
	return dp[t][k] = res;
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	memset(dp, -1, sizeof dp);
	int N;cin >> N;
	for(int i = 1;i <= N; ++ i)cin >> a[i];
	for(int k = 1;k <= N; ++ k)cout << dfs(N, min(2 * k, N - 2)) << '\n';
	return 0;
}