The 2022 ICPC Asia Regionals Online Contest (II)B Non-decreasing Array(DP)

发布于 2022-09-27  323 次阅读


在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;
}
19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-09-27