在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; }
Comments NOTHING