ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 正文

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

2022年9月27日 220点热度 1人点赞 0条评论

在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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: 暂无
最后更新:2022年9月27日

Eriktse

19岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌选手,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

订阅本站
Loading
文章目录
  • 题目大意 / Problem
  • 思路 / Thought

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

赣ICP备2022001555号-1

赣公网安备 36092402000057号