在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;
}
文章评论