专栏文章

题解：CF788A Functions again

RRex01
CF788A题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq145au
此快照首次捕获于
2025/12/03 21:14
3 个月前
此快照最后确认于
2025/12/03 21:14
3 个月前
查看原文

CF788A 题目传送门

题目大意

定义一个函数，函数如下：f(l,r)=∑i=lr−1∣ai−ai+1∣⋅(−1)i−lf(l,r) = \sum\limits_{i = l}^{r - 1 }|a_i−a_{i+1}| \cdot (−1)^{i−l}，而 1≤l≤r≤n1 \leq l \leq r \leq n，其中 nn 是数组 aa 的大小，∣x∣|x| 表示 xx 的绝对值。现在给你一个函数，请取恰当的 l,rl,r 使 ff 值最大，并输出最大的 ff 值。

解决思路

直接考虑动态规划，令 fi,0f_{i,0} 表示以 ii 为结尾，第 ii 位为 ++ 号；令 fi,1f_{i,1} 表示以 ii 为结尾，第 ii 位为 −- 号。然后通过计算两个相邻的数的差值，存入数组 dpdp，随后用得到的状态转移方程求出最大值。
CPP
f[i][0] = max(dp[i], f[i - 1][1] + dp[i]);
f[i][1] = max(0ll, f[i - 1][0] - dp[i]);
//状态转移方程求最大值
最后再来一重循环求答案的最大值即可。

注意事项

−109≤ai≤109-10^9 \leq a_i \leq 10^9，需要开 long long。

代码展示

CPP
#include <iostream>
#define ll long long
//不开long long见祖宗
using namespace std;

const int N = 1e5 + 10;
ll n, a[N], dp[N];
ll f[N][2], ans;
//f[i][j]表示以i为结尾并且第i位的符号为j

int main()
{
	scanf("%lld", &n);//建议scanf,更快
	for(int i = 1; i <= n; i++)
		scanf("%lld", &a[i]);
	for(int i = 1; i <= n; i++)
		dp[i] = abs(a[i] - a[i + 1]);//简化公式，加快速度
	for(int i = 1; i <= n; i++)
	{
		f[i][0] = max(dp[i], f[i - 1][1] + dp[i]);
		f[i][1] = max(0ll, f[i - 1][0] - dp[i]);
		//状态转移方程求最大值
	}
	for(int i = 1; i < n; i++) //求最大值 
		ans = max(max(f[i][0], f[i][1]), ans);
	printf("%lld\n", ans);//建议printf,更快
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...