【51Nod】1270 - 数组的最大代价（dp）

FishWang

发布于 2025-08-27 10:13:44

12500

代码可运行

运行总次数：0

代码可运行

点击打开题目

1270 数组的最大代价

题目来源： HackerRank

基准时间限制：1 秒空间限制：131072 KB 分值: 20 难度：3级算法题

取消关注

数组A包含N个元素A1, A2......AN。数组B包含N个元素B1, B2......BN。并且数组A中的每一个元素Ai，都满足1 <= Ai <= Bi。数组A的代价定义如下：

（公式表示所有两个相邻元素的差的绝对值之和）

给出数组B，计算可能的最大代价S。

Input

第1行：1个数N，表示数组的长度(1 <= N <= 50000)。
第2 - N+1行：每行1个数，对应数组元素Bi(1 <= Bi <= 10000)。

Output

输出最大代价S。

Input示例

Output示例

每个数的值不是最小值（1）就是最大值（b[i]）（我也不知道怎么去证明，但是想想，让绝对值的和最大，那么肯定是把距离拉开最大才能加到一个最大的和），那么我们就用dp，得出该位置如果是最小值和最大值可以形成的最大值，最后输出max(dp[n][0] , dp[n][1])即可

代码如下：

#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
int main()
{
	int n;
	int num[50011];
	int dp[50011][2];		//要么峰值要么谷值
	CLR(dp,0);
	scanf ("%d",&n);
	for (int i = 1 ; i <= n ; i++)
		scanf ("%d",&num[i]);
	dp[1][0] = dp[1][1] = 0;
	for (int i = 2 ; i <= n ; i++)
	{
		dp[i][0] = max (dp[i-1][0] , dp[i-1][1] + abs(1 - num[i-1]));
		dp[i][1] = max (dp[i-1][1] + abs(num[i] - num[i-1]) , dp[i-1][0] + num[i] - 1);
	}
	printf ("%d\n",max(dp[n][0] , dp[n][1]));
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

数组